mcs/class/corlib/Mono.Globalization.Unicode/SimpleCollator.cs

   1 //
   2 // SimpleCollator.cs : the core collator implementation
   3 //
   4 // Author:
   5 //      Atsushi Enomoto  <atsushi@ximian.com>
   6 //
   7 // Copyright (C) 2005 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 //
  30 // Here's a summary for supporting contractions, expansions and diacritical
  31 // remappings.
  32 //
  33 // Diacritical mapping is a simple tailoring rule that "remaps" diacritical
  34 // weight value from one to another. For now it applies to all range of
  35 // characters, but at some stage we might need to limit the remapping ranges.
  36 //
  37 // A Contraction consists of a string (actually char[]) and a sortkey entry
  38 // (i.e. byte[]). It indicates that a sequence of characters is interpreted
  39 // as a single character that has the mapped sortkey value. There is no
  40 // character which goes across "special rules". When the collator encountered
  41 // such a sequence of characters, it just returns the sortkey value without
  42 // further replacement.
  43 //
  44 // Since it is still likely to happen that a contraction sequence matches
  45 // other character than the identical sequence (depending on CompareOptions
  46 // and of course, defined sortkey value itself), comparison cannot be done
  47 // at source char[] level.
  48 //
  49 // In IndexOf(), the first character in the target string or the target char
  50 // itself is turned into sortkey bytes. If the character has a contraction and
  51 // that is sortkey map, then it is used instead. If the contraction exists and
  52 // that is replacement map, then the first character of the replacement string
  53 // is searched instead. IndexOf() always searches only for the top character,
  54 // and if it returned negative value, then it returns -1. Otherwise, it then
  55 // tries IsPrefix() from that location. If it returns true, then it returns
  56 // the index.
  57 //
  58 // LAMESPEC: IndexOf() is lame as a whole API. It never matches in the middle
  59 // of expansion and there is no proper way to return such indexes within
  60 // a single int return value.
  61 //
  62 // For example, try below in .NET:
  63 //      IndexOf("\u00E6", "a")
  64 //      IndexOf("\u00E6", "e")
  65 //
  66
  67
  68 using System;
  69 using System.Collections;
  70 using System.Globalization;
  71
  72 using Uni = Mono.Globalization.Unicode.MSCompatUnicodeTable;
  73 using UUtil = Mono.Globalization.Unicode.MSCompatUnicodeTableUtil;
  74 using COpt = System.Globalization.CompareOptions;
  75
  76 namespace Mono.Globalization.Unicode
  77 {
  78         internal class SimpleCollator
  79         {
  80                 // this environment variable is for debugging quick check.
  81 #pragma warning disable 169, 414
  82                 static bool QuickCheckDisabled =
  83                         Environment.internalGetEnvironmentVariable (
  84                         "MONO_COLLATION_QUICK_CHECK_DISABLED") == "yes";
  85 #pragma warning restore 169, 414
  86
  87                 unsafe internal struct Context
  88                 {
  89                         public Context (CompareOptions opt, byte* alwaysMatchFlags, byte* neverMatchFlags, byte* buffer1, byte* buffer2, byte* prev1/*, bool quickCheckPossible*/)
  90                         {
  91                                 Option = opt;
  92                                 AlwaysMatchFlags = alwaysMatchFlags;
  93                                 NeverMatchFlags = neverMatchFlags;
  94                                 Buffer1 = buffer1;
  95                                 Buffer2 = buffer2;
  96                                 PrevSortKey = prev1;
  97                                 PrevCode = -1;
  98 //                              QuickCheckPossible = quickCheckPossible;
  99                         }
 100
 101                         public readonly CompareOptions Option;
 102                         public readonly byte* NeverMatchFlags;
 103                         public readonly byte* AlwaysMatchFlags;
 104                         public byte* Buffer1;
 105                         public byte* Buffer2;
 106                         public int PrevCode;
 107                         public byte* PrevSortKey;
 108 //                      public readonly bool QuickCheckPossible;
 109
 110                         public void ClearPrevInfo ()
 111                         {
 112                                 PrevCode = -1;
 113                                 PrevSortKey = null;
 114                         }
 115                 }
 116
 117                 unsafe struct PreviousInfo
 118                 {
 119                         public int Code;
 120                         public byte* SortKey;
 121
 122                         public PreviousInfo (bool dummy)
 123                         {
 124                                 Code = -1;
 125                                 SortKey = null;
 126                         }
 127                 }
 128
 129                 struct Escape
 130                 {
 131                         public string Source;
 132                         public int Index;
 133                         public int Start;
 134                         public int End;
 135                         public int Optional;
 136                 }
 137
 138                 static SimpleCollator invariant =
 139                         new SimpleCollator (CultureInfo.InvariantCulture);
 140
 141                 readonly TextInfo textInfo; // for ToLower().
 142                 readonly CodePointIndexer cjkIndexer;
 143                 readonly Contraction [] contractions;
 144                 readonly Level2Map [] level2Maps;
 145                 // This flag marks characters as "unsafe", where the character
 146                 // could be used as part of a contraction (whose length > 1).
 147                 readonly byte [] unsafeFlags;
 148
 149                 unsafe readonly byte* cjkCatTable;
 150                 unsafe readonly byte* cjkLv1Table;
 151                 unsafe readonly byte* cjkLv2Table;
 152                 readonly CodePointIndexer cjkLv2Indexer;
 153                 readonly int lcid;
 154                 readonly bool frenchSort;
 155
 156
 157                 const int UnsafeFlagLength = 0x300 / 8;
 158
 159 //              readonly byte [] contractionFlags = new byte [16];
 160
 161                 // This array is internally used inside IndexOf() to store
 162                 // "no need to check" ASCII characters.
 163                 //
 164                 // Now that it should be thread safe, this array is allocated
 165                 // at every time.
 166 //              byte [] neverMatchFlags = new byte [128 / 8];
 167
 168                 #region .ctor() and split functions
 169
 170                 public SimpleCollator (CultureInfo culture)
 171                 {
 172                         lcid = culture.LCID;
 173                         textInfo = culture.TextInfo;
 174
 175                         unsafe {
 176                                 SetCJKTable (culture, ref cjkIndexer,
 177                                         ref cjkCatTable, ref cjkLv1Table,
 178                                         ref cjkLv2Indexer, ref cjkLv2Table);
 179                         }
 180
 181                         // Get tailoring info
 182                         TailoringInfo t = null;
 183                         for (CultureInfo ci = culture; ci.LCID != 127; ci = ci.Parent) {
 184                                 t = Uni.GetTailoringInfo (ci.LCID);
 185                                 if (t != null)
 186                                         break;
 187                         }
 188                         if (t == null) // then use invariant
 189                                 t = Uni.GetTailoringInfo (127);
 190
 191                         frenchSort = t.FrenchSort;
 192                         Uni.BuildTailoringTables (culture, t, ref contractions,
 193                                 ref level2Maps);
 194                         unsafeFlags = new byte [UnsafeFlagLength];
 195                         foreach (Contraction c in contractions) {
 196                                 if (c.Source.Length > 1)
 197                                         foreach (char ch in c.Source)
 198                                                 unsafeFlags [(int) ch / 8 ]
 199                                                         |= (byte) (1 << ((int) ch & 7));
 200 //                              for (int i = 0; i < c.Source.Length; i++) {
 201 //                                      int ch = c.Source [i];
 202 //                                      if (ch > 127)
 203 //                                              continue;
 204 //                                      contractionFlags [ch / 8] |= (byte) (1 << (ch & 7));
 205 //                              }
 206                         }
 207                         if (lcid != 127)
 208                                 foreach (Contraction c in invariant.contractions) {
 209                                         if (c.Source.Length > 1)
 210                                                 foreach (char ch in c.Source)
 211                                                         unsafeFlags [(int) ch / 8 ]
 212                                                                 |= (byte) (1 << ((int) ch & 7));
 213 //                                      for (int i = 0; i < c.Source.Length; i++) {
 214 //                                              int ch = c.Source [i];
 215 //                                              if (ch > 127)
 216 //                                                      continue;
 217 //                                              contractionFlags [ch / 8] |= (byte) (1 << (ch & 7));
 218 //                                      }
 219                                 }
 220
 221                         // FIXME: Since tailorings are mostly for latin
 222                         // (and in some cases Cyrillic) characters, it would
 223                         // be much better for performance to store "start
 224                         // indexes" for > 370 (culture-specific letters).
 225
 226 /*
 227 // dump tailoring table
 228 Console.WriteLine ("******** building table for {0} : contractions - {1} diacritical - {2}",
 229 culture.LCID, contractions.Length, level2Maps.Length);
 230 foreach (Contraction c in contractions) {
 231 foreach (char cc in c.Source)
 232 Console.Write ("{0:X4} ", (int) cc);
 233 Console.WriteLine (" -> '{0}'", c.Replacement);
 234 }
 235 */
 236                 }
 237
 238                 unsafe private void SetCJKTable (
 239                         CultureInfo culture, ref CodePointIndexer cjkIndexer,
 240                         ref byte* catTable, ref byte* lv1Table,
 241                         ref CodePointIndexer lv2Indexer, ref byte* lv2Table)
 242                 {
 243                         string name = GetNeutralCulture (culture).Name;
 244
 245                         Uni.FillCJK (name, ref cjkIndexer, ref catTable,
 246                                 ref lv1Table, ref lv2Indexer, ref lv2Table);
 247                 }
 248
 249                 static CultureInfo GetNeutralCulture (CultureInfo info)
 250                 {
 251                         CultureInfo ret = info;
 252                         while (ret.Parent != null && ret.Parent.LCID != 127)
 253                                 ret = ret.Parent;
 254                         return ret;
 255                 }
 256
 257                 #endregion
 258
 259                 unsafe byte Category (int cp)
 260                 {
 261                         if (cp < 0x3000 || cjkCatTable == null)
 262                                 return Uni.Category (cp);
 263                         int idx = cjkIndexer.ToIndex (cp);
 264                         return idx < 0 ? Uni.Category (cp) : cjkCatTable [idx];
 265                 }
 266
 267                 unsafe byte Level1 (int cp)
 268                 {
 269                         if (cp < 0x3000 || cjkLv1Table == null)
 270                                 return Uni.Level1 (cp);
 271                         int idx = cjkIndexer.ToIndex (cp);
 272                         return idx < 0 ? Uni.Level1 (cp) : cjkLv1Table [idx];
 273                 }
 274
 275                 unsafe byte Level2 (int cp, ExtenderType ext)
 276                 {
 277                         if (ext == ExtenderType.Buggy)
 278                                 return 5;
 279                         else if (ext == ExtenderType.Conditional)
 280                                 return 0;
 281
 282                         if (cp < 0x3000 || cjkLv2Table == null)
 283                                 return Uni.Level2 (cp);
 284                         int idx = cjkLv2Indexer.ToIndex (cp);
 285                         byte ret = idx < 0 ? (byte) 0 : cjkLv2Table [idx];
 286                         if (ret != 0)
 287                                 return ret;
 288                         ret = Uni.Level2 (cp);
 289                         if (level2Maps.Length == 0)
 290                                 return ret;
 291                         for (int i = 0; i < level2Maps.Length; i++) {
 292                                 if (level2Maps [i].Source == ret)
 293                                         return level2Maps [i].Replace;
 294                                 else if (level2Maps [i].Source > ret)
 295                                         break;
 296                         }
 297                         return ret;
 298                 }
 299
 300                 static bool IsHalfKana (int cp, COpt opt)
 301                 {
 302                         return (opt & COpt.IgnoreWidth) != 0 ||
 303                                 Uni.IsHalfWidthKana ((char) cp);
 304                 }
 305
 306                 Contraction GetContraction (string s, int start, int end)
 307                 {
 308 //                      int si = s [start];
 309 //                      if (si < 128 && (contractionFlags [si / 8] & (1 << (si & 7))) == 0)
 310 //                              return null;
 311                         Contraction c = GetContraction (s, start, end, contractions);
 312                         if (c != null || lcid == 127)
 313                                 return c;
 314                         return GetContraction (s, start, end, invariant.contractions);
 315                 }
 316
 317                 Contraction GetContraction (string s, int start, int end, Contraction [] clist)
 318                 {
 319                         for (int i = 0; i < clist.Length; i++) {
 320                                 Contraction ct = clist [i];
 321                                 int diff = ct.Source [0] - s [start];
 322                                 if (diff > 0)
 323                                         return null; // it's already sorted
 324                                 else if (diff < 0)
 325                                         continue;
 326                                 char [] chars = ct.Source;
 327                                 if (end - start < chars.Length)
 328                                         continue;
 329                                 bool match = true;
 330                                 for (int n = 0; n < chars.Length; n++)
 331                                         if (s [start + n] != chars [n]) {
 332                                                 match = false;
 333                                                 break;
 334                                         }
 335                                 if (match)
 336                                         return ct;
 337                         }
 338                         return null;
 339                 }
 340
 341                 Contraction GetTailContraction (string s, int start, int end)
 342                 {
 343 //                      int si = s [end - 1];
 344 //                      if (si < 128 && (contractionFlags [si / 8] & (1 << (si & 7))) == 0)
 345 //                              return null;
 346                         Contraction c = GetTailContraction (s, start, end, contractions);
 347                         if (c != null || lcid == 127)
 348                                 return c;
 349                         return GetTailContraction (s, start, end, invariant.contractions);
 350                 }
 351
 352                 Contraction GetTailContraction (string s, int start, int end, Contraction [] clist)
 353                 {
 354                         if (start == end || end < -1 || start >= s.Length || s.Length <= end + 1)
 355                                 throw new SystemException (String.Format ("MONO internal error. Failed to get TailContraction. start = {0} end = {1} string = '{2}'", start, end, s));
 356                         for (int i = 0; i < clist.Length; i++) {
 357                                 Contraction ct = clist [i];
 358                                 char [] chars = ct.Source;
 359                                 if (chars.Length > start - end)
 360                                         continue;
 361                                 if (chars [chars.Length - 1] != s [start])
 362                                         continue;
 363
 364                                 bool match = true;
 365                                 for (int n = 0, spos = start - chars.Length + 1;
 366                                      n < chars.Length;
 367                                      n++, spos++) {
 368                                         if (s [spos] != chars [n]) {
 369                                                 match = false;
 370                                                 break;
 371                                         }
 372                                 }
 373                                 if (match)
 374                                         return ct;
 375                         }
 376                         return null;
 377                 }
 378
 379                 Contraction GetContraction (char c)
 380                 {
 381                         Contraction ct = GetContraction (c, contractions);
 382                         if (ct != null || lcid == 127)
 383                                 return ct;
 384                         return GetContraction (c, invariant.contractions);
 385                 }
 386
 387                 Contraction GetContraction (char c, Contraction [] clist)
 388                 {
 389                         for (int i = 0; i < clist.Length; i++) {
 390                                 Contraction ct = clist [i];
 391                                 if (ct.Source [0] > c)
 392                                         return null; // it's already sorted
 393                                 if (ct.Source [0] == c && ct.Source.Length == 1)
 394                                         return ct;
 395                         }
 396                         return null;
 397                 }
 398
 399                 int FilterOptions (int i, COpt opt)
 400                 {
 401                         if ((opt & COpt.IgnoreWidth) != 0) {
 402                                 int x = Uni.ToWidthCompat (i);
 403                                 if (x != 0)
 404                                         i = x;
 405                         }
 406                         if ((opt & COpt.OrdinalIgnoreCase) != 0)
 407                                 i = textInfo.ToLower ((char) i);
 408                         if ((opt & COpt.IgnoreCase) != 0)
 409                                 i = textInfo.ToLower ((char) i);
 410                         if ((opt & COpt.IgnoreKanaType) != 0)
 411                                 i = Uni.ToKanaTypeInsensitive (i);
 412                         return i;
 413                 }
 414
 415                 enum ExtenderType {
 416                         None,
 417                         Simple,
 418                         Voiced,
 419                         Conditional,
 420                         Buggy,
 421                 }
 422
 423                 ExtenderType GetExtenderType (int i)
 424                 {
 425                         // LAMESPEC: Windows expects true for U+3005, but
 426                         // sometimes it does not represent to repeat just
 427                         // one character.
 428                         // Windows also expects true for U+3031 and U+3032,
 429                         // but they should *never* repeat one character.
 430
 431                         // U+2015 becomes an extender only when it is Japanese
 432                         if (i == 0x2015)
 433                                 return lcid == 16 ? ExtenderType.Conditional :
 434                                         ExtenderType.None;
 435
 436                         if (i < 0x3005 || i > 0xFF70)
 437                                 return ExtenderType.None;
 438                         if (i >= 0xFE7C) {
 439                                 switch (i) {
 440                                 case 0xFE7C:
 441                                 case 0xFE7D:
 442                                         return ExtenderType.Simple;
 443                                 case 0xFF70:
 444                                         return ExtenderType.Conditional;
 445                                 case 0xFF9E:
 446                                 case 0xFF9F:
 447                                         return ExtenderType.Voiced;
 448                                 }
 449                         }
 450                         if (i > 0x30FE)
 451                                 return ExtenderType.None;
 452                         switch (i) {
 453                         case 0x3005: // LAMESPEC: see above.
 454                                 return ExtenderType.Buggy;
 455                         case 0x3031: // LAMESPEC: see above.
 456                         case 0x3032: // LAMESPEC: see above.
 457                         case 0x309D:
 458                         case 0x30FD:
 459                                 return ExtenderType.Simple;
 460                         case 0x309E:
 461                         case 0x30FE:
 462                                 return ExtenderType.Voiced;
 463                         case 0x30FC:
 464                                 return ExtenderType.Conditional;
 465                         default:
 466                                 return ExtenderType.None;
 467                         }
 468                 }
 469
 470                 static byte ToDashTypeValue (ExtenderType ext, COpt opt)
 471                 {
 472                         if ((opt & COpt.IgnoreNonSpace) != 0) // LAMESPEC: huh, why?
 473                                 return 3;
 474                         switch (ext) {
 475                         case ExtenderType.None:
 476                                 return 3;
 477                         case ExtenderType.Conditional:
 478                                 return 5;
 479                         default:
 480                                 return 4;
 481                         }
 482                 }
 483
 484                 int FilterExtender (int i, ExtenderType ext, COpt opt)
 485                 {
 486                         if (ext == ExtenderType.Conditional &&
 487                                 Uni.HasSpecialWeight ((char) i)) {
 488                                 bool half = IsHalfKana ((char) i, opt);
 489                                 bool katakana = !Uni.IsHiragana ((char) i);
 490                                 switch (Level1 (i) & 7) {
 491                                 case 2:
 492                                         return half ? 0xFF71 : katakana ? 0x30A2 : 0x3042;
 493                                 case 3:
 494                                         return half ? 0xFF72 : katakana ? 0x30A4 : 0x3044;
 495                                 case 4:
 496                                         return half ? 0xFF73 : katakana ? 0x30A6 : 0x3046;
 497                                 case 5:
 498                                         return half ? 0xFF74 : katakana ? 0x30A8 : 0x3048;
 499                                 case 6:
 500                                         return half ? 0xFF75 : katakana ? 0x30AA : 0x304A;
 501                                 }
 502                         }
 503                         return i;
 504                 }
 505
 506                 static bool IsIgnorable (int i, COpt opt)
 507                 {
 508                         return Uni.IsIgnorable (i, (byte) (1 +
 509                                 ((opt & COpt.IgnoreSymbols) != 0 ? 2 : 0) +
 510                                 ((opt & COpt.IgnoreNonSpace) != 0 ? 4 : 0)));
 511
 512                 }
 513
 514                 bool IsSafe (int i)
 515                 {
 516                         return i / 8 >= unsafeFlags.Length ? true : (unsafeFlags [i / 8] & (1 << (i % 8))) == 0;
 517                 }
 518
 519                 #region GetSortKey()
 520
 521                 public SortKey GetSortKey (string s)
 522                 {
 523                         return GetSortKey (s, CompareOptions.None);
 524                 }
 525
 526                 public SortKey GetSortKey (string s, CompareOptions options)
 527                 {
 528                         return GetSortKey (s, 0, s.Length, options);
 529                 }
 530
 531                 public SortKey GetSortKey (string s, int start, int length, CompareOptions options)
 532                 {
 533                         SortKeyBuffer buf = new SortKeyBuffer (lcid);
 534                         buf.Initialize (options, lcid, s, frenchSort);
 535                         int end = start + length;
 536                         GetSortKey (s, start, end, buf, options);
 537                         return buf.GetResultAndReset ();
 538                 }
 539
 540                 unsafe void GetSortKey (string s, int start, int end,
 541                         SortKeyBuffer buf, CompareOptions opt)
 542                 {
 543                         byte* prevbuf = stackalloc byte [4];
 544                         ClearBuffer (prevbuf, 4);
 545                         Context ctx = new Context (opt, null, null, null, null, prevbuf);
 546
 547                         for (int n = start; n < end; n++) {
 548                                 int i = s [n];
 549
 550                                 ExtenderType ext = GetExtenderType (i);
 551                                 if (ext != ExtenderType.None) {
 552                                         i = FilterExtender (ctx.PrevCode, ext, opt);
 553                                         if (i >= 0)
 554                                                 FillSortKeyRaw (i, ext, buf, opt);
 555                                         else if (ctx.PrevSortKey != null) {
 556                                                 byte* b = ctx.PrevSortKey;
 557                                                 buf.AppendNormal (
 558                                                         b [0],
 559                                                         b [1],
 560                                                         b [2] != 1 ? b [2] : Level2 (i, ext),
 561                                                         b [3] != 1 ? b [3] : Uni.Level3 (i));
 562                                         }
 563                                         // otherwise do nothing.
 564                                         // (if the extender is the first char
 565                                         // in the string, then just ignore.)
 566                                         continue;
 567                                 }
 568
 569                                 if (IsIgnorable (i, opt))
 570                                         continue;
 571                                 i = FilterOptions (i, opt);
 572
 573                                 Contraction ct = GetContraction (s, n, end);
 574                                 if (ct != null) {
 575                                         if (ct.Replacement != null) {
 576                                                 GetSortKey (ct.Replacement, 0, ct.Replacement.Length, buf, opt);
 577                                         } else {
 578                                                 byte* b = ctx.PrevSortKey;
 579                                                 for (int bi = 0; bi < ct.SortKey.Length; bi++)
 580                                                         b [bi] = ct.SortKey [bi];
 581                                                 buf.AppendNormal (
 582                                                         b [0],
 583                                                         b [1],
 584                                                         b [2] != 1 ? b [2] : Level2 (i, ext),
 585                                                         b [3] != 1 ? b [3] : Uni.Level3 (i));
 586                                                 ctx.PrevCode = -1;
 587                                         }
 588                                         n += ct.Source.Length - 1;
 589                                 }
 590                                 else {
 591                                         if (!Uni.IsIgnorableNonSpacing (i))
 592                                                 ctx.PrevCode = i;
 593                                         FillSortKeyRaw (i, ExtenderType.None, buf, opt);
 594                                 }
 595                         }
 596                 }
 597
 598                 void FillSortKeyRaw (int i, ExtenderType ext,
 599                         SortKeyBuffer buf, CompareOptions opt)
 600                 {
 601                         if (0x3400 <= i && i <= 0x4DB5) {
 602                                 int diff = i - 0x3400;
 603                                 buf.AppendCJKExtension (
 604                                         (byte) (0x10 + diff / 254),
 605                                         (byte) (diff % 254 + 2));
 606                                 return;
 607                         }
 608
 609                         UnicodeCategory uc = char.GetUnicodeCategory ((char) i);
 610                         switch (uc) {
 611                         case UnicodeCategory.PrivateUse:
 612                                 int diff = i - 0xE000;
 613                                 buf.AppendNormal (
 614                                         (byte) (0xE5 + diff / 254),
 615                                         (byte) (diff % 254 + 2),
 616                                         0,
 617                                         0);
 618                                 return;
 619                         case UnicodeCategory.Surrogate:
 620                                 FillSurrogateSortKeyRaw (i, buf);
 621                                 return;
 622                         }
 623
 624                         byte level2 = Level2 (i, ext);
 625                         if (Uni.HasSpecialWeight ((char) i)) {
 626                                 byte level1 = Level1 (i);
 627                                 buf.AppendKana (
 628                                         Category (i),
 629                                         level1,
 630                                         level2,
 631                                         Uni.Level3 (i),
 632                                         Uni.IsJapaneseSmallLetter ((char) i),
 633                                         ToDashTypeValue (ext, opt),
 634                                         !Uni.IsHiragana ((char) i),
 635                                         IsHalfKana ((char) i, opt)
 636                                         );
 637                                 if ((opt & COpt.IgnoreNonSpace) == 0 && ext == ExtenderType.Voiced)
 638                                         // Append voice weight
 639                                         buf.AppendNormal (1, 1, 1, 0);
 640                         }
 641                         else
 642                                 buf.AppendNormal (
 643                                         Category (i),
 644                                         Level1 (i),
 645                                         level2,
 646                                         Uni.Level3 (i));
 647                 }
 648
 649                 void FillSurrogateSortKeyRaw (int i, SortKeyBuffer buf)
 650                 {
 651                         int diffbase = 0;
 652                         int segment = 0;
 653                         byte lower = 0;
 654
 655                         if (i < 0xD840) {
 656                                 diffbase = 0xD800;
 657                                 segment = 0x41;
 658                                 lower = (byte) ((i == 0xD800) ? 0x3E : 0x3F);
 659                         } else if (0xD840 <= i && i < 0xD880) {
 660                                 diffbase = 0xD840;
 661                                 segment = 0xF2;
 662                                 lower = 0x3E;
 663                         } else if (0xDB80 <= i && i < 0xDC00) {
 664                                 diffbase = 0xDB80 - 0x40;
 665                                 segment = 0xFE;
 666                                 lower = 0x3E;
 667                         } else {
 668                                 diffbase = 0xDC00 - 0xF8 + 2;
 669                                 segment = 0x41;
 670                                 lower = 0x3F;
 671                         }
 672                         int diff = i - diffbase;
 673
 674                         buf.AppendNormal (
 675                                 (byte) (segment + diff / 254),
 676                                 (byte) (diff % 254 + 2),
 677                                 lower,
 678                                 lower);
 679                 }
 680
 681                 #endregion
 682
 683                 #region Compare()
 684
 685                 public int Compare (string s1, string s2)
 686                 {
 687                         return Compare (s1, 0, s1.Length, s2, 0, s2.Length, CompareOptions.None);
 688                 }
 689 /*
 690                 private int CompareOrdinal (string s1, int idx1, int len1,
 691                         string s2, int idx2, int len2)
 692                 {
 693                         int min = len1 < len2 ? len1 : len2;
 694                         int end1 = idx1 + min;
 695                         int end2 = idx2 + min;
 696                         if (idx1 < 0 || idx2 < 0 || end1 > s1.Length || end2 > s2.Length)
 697                                 throw new SystemException (String.Format ("CompareInfo Internal Error: Should not happen. {0} {1} {2} {3} {4} {5}", idx1, idx2, len1, len2, s1.Length, s2.Length));
 698                         for (int i1 = idx1, i2 = idx2;
 699                                 i1 < end1 && i2 < end2; i1++, i2++)
 700                                 if (s1 [i1] != s2 [i2])
 701                                         return s1 [i1] - s2 [i2];
 702                         return len1 == len2 ? 0 :
 703                                 len1 == min ? - 1 : 1;
 704                 }
 705
 706                 // mostly equivalent to CompareOrdinal, but the return value is
 707                 // not based on codepoints.
 708                 private int CompareQuick (string s1, int idx1, int len1,
 709                         string s2, int idx2, int len2, out bool sourceConsumed,
 710                         out bool targetConsumed, bool immediateBreakup)
 711                 {
 712                         sourceConsumed = false;
 713                         targetConsumed = false;
 714                         int min = len1 < len2 ? len1 : len2;
 715                         int end1 = idx1 + min;
 716                         int end2 = idx2 + min;
 717                         if (idx1 < 0 || idx2 < 0 || end1 > s1.Length || end2 > s2.Length)
 718                                 throw new SystemException (String.Format ("CompareInfo Internal Error: Should not happen. {0} {1} {2} {3} {4} {5}", idx1, idx2, len1, len2, s1.Length, s2.Length));
 719                         for (int i1 = idx1, i2 = idx2;
 720                                 i1 < end1 && i2 < end2; i1++, i2++)
 721                                 if (s1 [i1] != s2 [i2]) {
 722                                         if (immediateBreakup)
 723                                                 return -1;
 724                                         int ret = Category (s1 [i1]) - Category (s2 [i2]);
 725                                         if (ret == 0)
 726                                                 ret = Level1 (s1 [i1]) - Level1 (s2 [i2]);
 727                                         // no level2 and 4
 728                                         if (ret == 0)
 729                                                 ret = Uni.Level3 (s1 [i1]) - Uni.Level3 (s2 [i2]);
 730                                         if (ret == 0)
 731                                                 throw new SystemException (String.Format ("CompareInfo Internal Error: Should not happen. '{0}' {2} {3} '{1}' {4} {5}", s1, s2, idx1, end1, idx2, end2));
 732                                         return ret;
 733                                 }
 734                         sourceConsumed = len1 <= len2;
 735                         targetConsumed = len1 >= len2;
 736                         return len1 == len2 ? 0 :
 737                                 len1 == min ? - 1 : 1;
 738                 }
 739
 740                 private int CompareOrdinalIgnoreCase (string s1, int idx1, int len1,
 741                         string s2, int idx2, int len2)
 742                 {
 743                         int min = len1 < len2 ? len1 : len2;
 744                         int end1 = idx1 + min;
 745                         int end2 = idx2 + min;
 746                         if (idx1 < 0 || idx2 < 0 || end1 > s1.Length || end2 > s2.Length)
 747                                 throw new SystemException (String.Format ("CompareInfo Internal Error: Should not happen. {0} {1} {2} {3} {4} {5}", idx1, idx2, len1, len2, s1.Length, s2.Length));
 748                         TextInfo ti = invariant.textInfo;
 749                         for (int i1 = idx1, i2 = idx2;
 750                                 i1 < end1 && i2 < end2; i1++, i2++)
 751                                 if (ti.ToLower (s1 [i1]) != ti.ToLower (s2 [i2]))
 752                                         return ti.ToLower (s1 [i1]) - ti.ToLower (s2 [i2]);
 753                         return len1 == len2 ? 0 :
 754                                 len1 == min ? - 1 : 1;
 755                 }
 756 */
 757                 internal unsafe int Compare (string s1, int idx1, int len1,
 758                         string s2, int idx2, int len2, CompareOptions options)
 759                 {
 760 #if false // stable easy version, depends on GetSortKey().
 761                         SortKey sk1 = GetSortKey (s1, idx1, len1, options);
 762                         SortKey sk2 = GetSortKey (s2, idx2, len2, options);
 763                         byte [] d1 = sk1.KeyData;
 764                         byte [] d2 = sk2.KeyData;
 765                         int len = d1.Length > d2.Length ? d2.Length : d1.Length;
 766                         for (int i = 0; i < len; i++)
 767                                 if (d1 [i] != d2 [i])
 768                                         return d1 [i] < d2 [i] ? -1 : 1;
 769                         return d1.Length == d2.Length ? 0 : d1.Length < d2.Length ? -1 : 1;
 770 #else
 771                         byte* sk1 = stackalloc byte [4];
 772                         byte* sk2 = stackalloc byte [4];
 773                         ClearBuffer (sk1, 4);
 774                         ClearBuffer (sk2, 4);
 775                         Context ctx = new Context (options, null, null, sk1, sk2, null);
 776                         //      QuickCheckPossible (s1, idx1, idx1 + len1, s2, idx2, idx2 + len2));
 777
 778                         bool dummy, dummy2;
 779                         int ret = CompareInternal (s1, idx1, len1, s2, idx2, len2, out dummy, out dummy2, true, false, ref ctx);
 780                         return ret == 0 ? 0 : ret < 0 ? -1 : 1;
 781 #endif
 782                 }
 783
 784                 unsafe void ClearBuffer (byte* buffer, int size)
 785                 {
 786                         for (int i = 0; i < size; i++)
 787                                 buffer [i] = 0;
 788                 }
 789
 790 /*
 791                 bool QuickCheckPossible (string s1, int idx1, int end1,
 792                         string s2, int idx2, int end2)
 793                 {
 794 #if true
 795                         // looks like it is buggy and inefficient, so just disable it.
 796                         return false;
 797 #else
 798                         if (QuickCheckDisabled)
 799                                 return false;
 800 //                      if (s1.Length > 100 || s2.Length > 100)
 801 //                              return false;
 802                         for (int i = idx1; i < end1; i++)
 803                                 if (s1 [i] < 0x20 && (s1 [i] < '\x9' || s1 [i] > '\xD') || s1 [i] >= 0x80 || s1 [i] == '-' || s1 [i] == '\'')
 804                                         return false;
 805                         for (int i = idx2; i < end2; i++)
 806                                 if (s2 [i] < 0x20 && (s2 [i] < '\x9' || s2 [i] > '\xD') || s2 [i] >= 0x80 || s2 [i] == '-' || s2 [i] == '\'')
 807                                         return false;
 808                         return true;
 809 #endif
 810                 }
 811 */
 812
 813                 unsafe int CompareInternal (string s1, int idx1, int len1, string s2,
 814                         int idx2, int len2,
 815                         out bool targetConsumed, out bool sourceConsumed,
 816                         bool skipHeadingExtenders, bool immediateBreakup,
 817                         ref Context ctx)
 818                 {
 819                         COpt opt = ctx.Option;
 820                         int start1 = idx1;
 821                         int start2 = idx2;
 822                         int end1 = idx1 + len1;
 823                         int end2 = idx2 + len2;
 824                         targetConsumed = false;
 825                         sourceConsumed = false;
 826                         PreviousInfo prev2 = new PreviousInfo (false);
 827
 828 //                      if (opt == CompareOptions.None && ctx.QuickCheckPossible)
 829 //                              return CompareQuick (s1, idx1, len1, s2, idx2, len2, out sourceConsumed, out targetConsumed, immediateBreakup);
 830
 831                         // It holds final result that comes from the comparison
 832                         // at level 2 or lower. Even if Compare() found the
 833                         // difference at level 2 or lower, it still has to
 834                         // continue level 1 comparison. FinalResult is used
 835                         // when there was no further differences.
 836                         int finalResult = 0;
 837                         // It holds the comparison level to do. It starts from
 838                         // 5, and becomes 1 when we do primary-only comparison.
 839                         int currentLevel = 5;
 840
 841                         int lv5At1 = -1;
 842                         int lv5At2 = -1;
 843                         int lv5Value1 = 0;
 844                         int lv5Value2 = 0;
 845
 846                         // Skip heading extenders
 847                         if (skipHeadingExtenders) {
 848                                 for (; idx1 < end1; idx1++)
 849                                         if (GetExtenderType (s1 [idx1]) == ExtenderType.None)
 850                                                 break;
 851                                 for (; idx2 < end2; idx2++)
 852                                         if (GetExtenderType (s2 [idx2]) == ExtenderType.None)
 853                                                 break;
 854                         }
 855
 856                         ExtenderType ext1 = ExtenderType.None;
 857                         ExtenderType ext2 = ExtenderType.None;
 858
 859                         int quickCheckPos1 = idx1;
 860                         int quickCheckPos2 = idx2;
 861                         bool stringSort = (opt & COpt.StringSort) != 0;
 862                         bool ignoreNonSpace = (opt & COpt.IgnoreNonSpace) != 0;
 863                         Escape escape1 = new Escape ();
 864                         Escape escape2 = new Escape ();
 865
 866                         while (true) {
 867                                 for (; idx1 < end1; idx1++)
 868                                         if (!IsIgnorable (s1 [idx1], opt))
 869                                                 break;
 870                                 for (; idx2 < end2; idx2++)
 871                                         if (!IsIgnorable (s2 [idx2], opt))
 872                                                 break;
 873
 874                                 if (idx1 >= end1) {
 875                                         if (escape1.Source == null)
 876                                                 break;
 877                                         s1 = escape1.Source;
 878                                         start1 = escape1.Start;
 879                                         idx1 = escape1.Index;
 880                                         end1 = escape1.End;
 881                                         quickCheckPos1 = escape1.Optional;
 882                                         escape1.Source = null;
 883                                         continue;
 884                                 }
 885                                 if (idx2 >= end2) {
 886                                         if (escape2.Source == null)
 887                                                 break;
 888                                         s2 = escape2.Source;
 889                                         start2 = escape2.Start;
 890                                         idx2 = escape2.Index;
 891                                         end2 = escape2.End;
 892                                         quickCheckPos2 = escape2.Optional;
 893                                         escape2.Source = null;
 894                                         continue;
 895                                 }
 896 #if true
 897 // If comparison is unstable, then this part is one of the most doubtful part.
 898 // Here we run quick codepoint comparison and run back to "stable" area to
 899 // compare characters.
 900
 901                                 // Strictly to say, even the first character
 902                                 // could be compared here, but it messed
 903                                 // backward step, so I just avoided mess.
 904                                 if (quickCheckPos1 < idx1 && quickCheckPos2 < idx2) {
 905                                         while (idx1 < end1 && idx2 < end2 &&
 906                                                 s1 [idx1] == s2 [idx2]) {
 907                                                 idx1++;
 908                                                 idx2++;
 909                                         }
 910                                         if (idx1 == end1 || idx2 == end2)
 911                                                 continue; // check replacement
 912
 913                                         int backwardEnd1 = quickCheckPos1;
 914                                         int backwardEnd2 = quickCheckPos2;
 915                                         quickCheckPos1 = idx1;
 916                                         quickCheckPos2 = idx2;
 917
 918                                         idx1--;
 919                                         idx2--;
 920
 921                                         for (;idx1 > backwardEnd1; idx1--)
 922                                                 if (Category (s1 [idx1]) != 1)
 923                                                         break;
 924                                         for (;idx2 > backwardEnd2; idx2--)
 925                                                 if (Category (s2 [idx2]) != 1)
 926                                                         break;
 927                                         for (;idx1 > backwardEnd1; idx1--)
 928                                                 if (IsSafe (s1 [idx1]))
 929                                                         break;
 930                                         for (;idx2 > backwardEnd2; idx2--)
 931                                                 if (IsSafe (s2 [idx2]))
 932                                                         break;
 933                                 }
 934 #endif
 935
 936                                 int cur1 = idx1;
 937                                 int cur2 = idx2;
 938                                 byte* sk1 = null;
 939                                 byte* sk2 = null;
 940                                 int i1 = FilterOptions (s1 [idx1], opt);
 941                                 int i2 = FilterOptions (s2 [idx2], opt);
 942                                 bool special1 = false;
 943                                 bool special2 = false;
 944
 945                                 // If current character is an expander, then
 946                                 // repeat the previous character.
 947                                 ext1 = GetExtenderType (i1);
 948                                 if (ext1 != ExtenderType.None) {
 949                                         if (ctx.PrevCode < 0) {
 950                                                 if (ctx.PrevSortKey == null) {
 951                                                         // nothing to extend
 952                                                         idx1++;
 953                                                         continue;
 954                                                 }
 955                                                 sk1 = ctx.PrevSortKey;
 956                                         }
 957                                         else
 958                                                 i1 = FilterExtender (ctx.PrevCode, ext1, opt);
 959                                 }
 960                                 ext2 = GetExtenderType (i2);
 961                                 if (ext2 != ExtenderType.None) {
 962                                         if (prev2.Code < 0) {
 963                                                 if (prev2.SortKey == null) {
 964                                                         // nothing to extend
 965                                                         idx2++;
 966                                                         continue;
 967                                                 }
 968                                                 sk2 = prev2.SortKey;
 969                                         }
 970                                         else
 971                                                 i2 = FilterExtender (prev2.Code, ext2, opt);
 972                                 }
 973
 974                                 byte cat1 = Category (i1);
 975                                 byte cat2 = Category (i2);
 976
 977                                 // Handle special weight characters
 978                                 if (cat1 == 6) {
 979                                         if (!stringSort && currentLevel == 5) {
 980                                                 lv5At1 = escape1.Source != null ?
 981                                                         escape1.Index - escape1.Start :
 982                                                         cur1 - start1;
 983                                                 // here Windows has a bug that it does
 984                                                 // not consider thirtiary weight.
 985                                                 lv5Value1 = Level1 (i1) << 8 + Uni.Level3 (i1);
 986                                         }
 987                                         ctx.PrevCode = i1;
 988                                         idx1++;
 989                                 }
 990                                 if (cat2 == 6) {
 991                                         if (!stringSort && currentLevel == 5) {
 992                                                 lv5At2 = escape2.Source != null ?
 993                                                         escape2.Index - escape2.Start :
 994                                                         cur2 - start2;
 995                                                 // here Windows has a bug that it does
 996                                                 // not consider thirtiary weight.
 997                                                 lv5Value2 = Level1 (i2) << 8 + Uni.Level3 (i2);
 998                                         }
 999                                         prev2.Code = i2;
1000                                         idx2++;
1001                                 }
1002                                 if (cat1 == 6 || cat2 == 6) {
1003                                         if (currentLevel == 5) {
1004                                                 if (lv5Value1 == lv5Value2) {
1005                                                         // There is not really difference here.
1006                                                         lv5At1 = lv5At2 = -1;
1007                                                         lv5Value1 = lv5Value2 = 0;
1008                                                 }
1009                                                 else
1010                                                         currentLevel = 4;
1011                                         }
1012                                         continue;
1013                                 }
1014
1015                                 Contraction ct1 = null;
1016                                 if (ext1 == ExtenderType.None)
1017                                         ct1 = GetContraction (s1, idx1, end1);
1018
1019                                 int offset1 = 1;
1020                                 if (sk1 != null)
1021                                         offset1 = 1;
1022                                 else if (ct1 != null) {
1023                                         offset1 = ct1.Source.Length;
1024                                         if (ct1.SortKey != null) {
1025                                                 sk1 = ctx.Buffer1;
1026                                                 for (int i = 0; i < ct1.SortKey.Length; i++)
1027                                                         sk1 [i] = ct1.SortKey [i];
1028                                                 ctx.PrevCode = -1;
1029                                                 ctx.PrevSortKey = sk1;
1030                                         }
1031                                         else if (escape1.Source == null) {
1032                                                 escape1.Source = s1;
1033                                                 escape1.Start = start1;
1034                                                 escape1.Index = cur1 + ct1.Source.Length;
1035                                                 escape1.End = end1;
1036                                                 escape1.Optional = quickCheckPos1;
1037                                                 s1 = ct1.Replacement;
1038                                                 idx1 = 0;
1039                                                 start1 = 0;
1040                                                 end1 = s1.Length;
1041                                                 quickCheckPos1 = 0;
1042                                                 continue;
1043                                         }
1044                                 }
1045                                 else {
1046                                         sk1 = ctx.Buffer1;
1047                                         sk1 [0] = cat1;
1048                                         sk1 [1] = Level1 (i1);
1049                                         if (!ignoreNonSpace && currentLevel > 1)
1050                                                 sk1 [2] = Level2 (i1, ext1);
1051                                         if (currentLevel > 2)
1052                                                 sk1 [3] = Uni.Level3 (i1);
1053                                         if (currentLevel > 3)
1054                                                 special1 = Uni.HasSpecialWeight ((char) i1);
1055                                         if (cat1 > 1)
1056                                                 ctx.PrevCode = i1;
1057                                 }
1058
1059                                 Contraction ct2 = null;
1060                                 if (ext2 == ExtenderType.None)
1061                                         ct2 = GetContraction (s2, idx2, end2);
1062
1063                                 if (sk2 != null)
1064                                         idx2++;
1065                                 else if (ct2 != null) {
1066                                         idx2 += ct2.Source.Length;
1067                                         if (ct2.SortKey != null) {
1068                                                 sk2 = ctx.Buffer2;
1069                                                 for (int i = 0; i < ct2.SortKey.Length; i++)
1070                                                         sk2 [i] = ct2.SortKey [i];
1071                                                 prev2.Code = -1;
1072                                                 prev2.SortKey = sk2;
1073                                         }
1074                                         else if (escape2.Source == null) {
1075                                                 escape2.Source = s2;
1076                                                 escape2.Start = start2;
1077                                                 escape2.Index = cur2 + ct2.Source.Length;
1078                                                 escape2.End = end2;
1079                                                 escape2.Optional = quickCheckPos2;
1080                                                 s2 = ct2.Replacement;
1081                                                 idx2 = 0;
1082                                                 start2 = 0;
1083                                                 end2 = s2.Length;
1084                                                 quickCheckPos2 = 0;
1085                                                 continue;
1086                                         }
1087                                 }
1088                                 else {
1089                                         sk2 = ctx.Buffer2;
1090                                         sk2 [0] = cat2;
1091                                         sk2 [1] = Level1 (i2);
1092                                         if (!ignoreNonSpace && currentLevel > 1)
1093                                                 sk2 [2] = Level2 (i2, ext2);
1094                                         if (currentLevel > 2)
1095                                                 sk2 [3] = Uni.Level3 (i2);
1096                                         if (currentLevel > 3)
1097                                                 special2 = Uni.HasSpecialWeight ((char) i2);
1098                                         if (cat2 > 1)
1099                                                 prev2.Code = i2;
1100                                         idx2++;
1101                                 }
1102
1103                                 // Add offset here so that it does not skip
1104                                 // idx1 while s2 has a replacement.
1105                                 idx1 += offset1;
1106
1107                                 if (!ignoreNonSpace) {
1108                                         // add diacritical marks in s1 here
1109                                         while (idx1 < end1) {
1110                                                 if (Category (s1 [idx1]) != 1)
1111                                                         break;
1112                                                 if (sk1 [2] == 0)
1113                                                         sk1 [2] = 2;
1114                                                 sk1 [2] = (byte) (sk1 [2] +
1115                                                         Level2 (s1 [idx1], ExtenderType.None));
1116                                                 idx1++;
1117                                         }
1118
1119                                         // add diacritical marks in s2 here
1120                                         while (idx2 < end2) {
1121                                                 if (Category (s2 [idx2]) != 1)
1122                                                         break;
1123                                                 if (sk2 [2] == 0)
1124                                                         sk2 [2] = 2;
1125                                                 sk2 [2] = (byte) (sk2 [2] +
1126                                                         Level2 (s2 [idx2], ExtenderType.None));
1127                                                 idx2++;
1128                                         }
1129                                 }
1130
1131                                 int ret = sk1 [0] - sk2 [0];
1132                                 ret = ret != 0 ? ret : sk1 [1] - sk2 [1];
1133                                 if (ret != 0)
1134                                         return ret;
1135                                 if (currentLevel == 1)
1136                                         continue;
1137                                 if (!ignoreNonSpace) {
1138                                         ret = sk1 [2] - sk2 [2];
1139                                         if (ret != 0) {
1140                                                 finalResult = ret;
1141                                                 if (immediateBreakup)
1142                                                         return -1; // different
1143                                                 currentLevel = frenchSort ? 2 : 1;
1144                                                 continue;
1145                                         }
1146                                 }
1147                                 if (currentLevel == 2)
1148                                         continue;
1149                                 ret = sk1 [3] - sk2 [3];
1150                                 if (ret != 0) {
1151                                         finalResult = ret;
1152                                         if (immediateBreakup)
1153                                                 return -1; // different
1154                                         currentLevel = 2;
1155                                         continue;
1156                                 }
1157                                 if (currentLevel == 3)
1158                                         continue;
1159                                 if (special1 != special2) {
1160                                         if (immediateBreakup)
1161                                                 return -1; // different
1162                                         finalResult = special1 ? 1 : -1;
1163                                         currentLevel = 3;
1164                                         continue;
1165                                 }
1166                                 if (special1) {
1167                                         ret = CompareFlagPair (
1168                                                 !Uni.IsJapaneseSmallLetter ((char) i1),
1169                                                 !Uni.IsJapaneseSmallLetter ((char) i2));
1170                                         ret = ret != 0 ? ret :
1171                                                 ToDashTypeValue (ext1, opt) -
1172                                                 ToDashTypeValue (ext2, opt);
1173                                         ret = ret != 0 ? ret : CompareFlagPair (
1174                                                 Uni.IsHiragana ((char) i1),
1175                                                 Uni.IsHiragana ((char) i2));
1176                                         ret = ret != 0 ? ret : CompareFlagPair (
1177                                                 !IsHalfKana ((char) i1, opt),
1178                                                 !IsHalfKana ((char) i2, opt));
1179                                         if (ret != 0) {
1180                                                 if (immediateBreakup)
1181                                                         return -1; // different
1182                                                 finalResult = ret;
1183                                                 currentLevel = 3;
1184                                                 continue;
1185                                         }
1186                                 }
1187                         }
1188
1189                         // If there were only level 3 or lower differences,
1190                         // then we still have to find diacritical differences
1191                         // if any.
1192                         if (!ignoreNonSpace &&
1193                                 finalResult != 0 && currentLevel > 2) {
1194                                 while (idx1 < end1 && idx2 < end2) {
1195                                         if (!Uni.IsIgnorableNonSpacing (s1 [idx1]))
1196                                                 break;
1197                                         if (!Uni.IsIgnorableNonSpacing (s2 [idx2]))
1198                                                 break;
1199                                         finalResult = Level2 (FilterOptions (s1 [idx1], opt), ext1) - Level2 (FilterOptions (s2 [idx2], opt), ext2);
1200                                         if (finalResult != 0)
1201                                                 break;
1202                                         idx1++;
1203                                         idx2++;
1204                                         // they should work only for the first character
1205                                         ext1 = ExtenderType.None;
1206                                         ext2 = ExtenderType.None;
1207                                 }
1208                         }
1209                         if (currentLevel == 1 && finalResult != 0) {
1210                                 while (idx1 < end1) {
1211                                         if (Uni.IsIgnorableNonSpacing (s1 [idx1]))
1212                                                 idx1++;
1213                                         else
1214                                                 break;
1215                                 }
1216                                 while (idx2 < end2) {
1217                                         if (Uni.IsIgnorableNonSpacing (s2 [idx2]))
1218                                                 idx2++;
1219                                         else
1220                                                 break;
1221                                 }
1222                         }
1223                         // we still have to check level 5
1224                         if (finalResult == 0) {
1225                                 if (lv5At1 < 0 && lv5At2 >= 0)
1226                                         finalResult = -1;
1227                                 else if (lv5At2 < 0 && lv5At1 >= 0)
1228                                         finalResult = 1;
1229                                 else {
1230                                         finalResult = lv5At1 - lv5At2;
1231                                         if (finalResult == 0)
1232                                                 finalResult = lv5Value1 - lv5Value2;
1233                                 }
1234                         }
1235                         if (finalResult == 0) {
1236                                 if (idx2 == end2)
1237                                         targetConsumed = true;
1238                                 if (idx1 == end1)
1239                                         sourceConsumed = true;
1240                         }
1241                         return idx1 != end1 ? 1 : idx2 == end2 ? finalResult : -1;
1242                 }
1243
1244                 int CompareFlagPair (bool b1, bool b2)
1245                 {
1246                         return b1 == b2 ? 0 : b1 ? 1 : -1;
1247                 }
1248
1249                 #endregion
1250
1251                 #region IsPrefix() and IsSuffix()
1252
1253                 public bool IsPrefix (string src, string target, CompareOptions opt)
1254                 {
1255                         return IsPrefix (src, target, 0, src.Length, opt);
1256                 }
1257
1258                 public unsafe bool IsPrefix (string s, string target, int start, int length, CompareOptions opt)
1259                 {
1260                         if (target.Length == 0)
1261                                 return true;
1262                         byte* sk1 = stackalloc byte [4];
1263                         byte* sk2 = stackalloc byte [4];
1264                         ClearBuffer (sk1, 4);
1265                         ClearBuffer (sk2, 4);
1266                         Context ctx = new Context (opt, null, null, sk1, sk2, null);
1267                                 //QuickCheckPossible (s, start, start + length, target, 0, target.Length));
1268                         return IsPrefix (s, target, start, length, true, ref ctx);
1269                 }
1270
1271                 unsafe bool IsPrefix (string s, string target, int start, int length, bool skipHeadingExtenders, ref Context ctx)
1272                 {
1273                         bool consumed, dummy;
1274                         CompareInternal (s, start, length,
1275                                 target, 0, target.Length,
1276                                 out consumed, out dummy, skipHeadingExtenders,
1277                                 true, ref ctx);
1278                         return consumed;
1279                 }
1280
1281                 // IsSuffix()
1282
1283                 public bool IsSuffix (string src, string target, CompareOptions opt)
1284                 {
1285                         return IsSuffix (src, target, src.Length - 1, src.Length, opt);
1286                 }
1287
1288                 public unsafe bool IsSuffix (string s, string target, int start, int length, CompareOptions opt)
1289                 {
1290                         if (target.Length == 0)
1291                                 return true;
1292                         int last = LastIndexOf (s, target, start, length, opt);
1293                         return last >= 0 && Compare (s, last, s.Length - last, target, 0, target.Length, opt) == 0;
1294 /*
1295                         // quick check : simple codepoint comparison
1296                         if (s.Length >= target.Length) {
1297                                 int si = start;
1298                                 int se = start - length;
1299                                 for (int i = target.Length - 1; si >= se && i >= 0; i--, si--)
1300                                         if (s [si] != target [i])
1301                                                 break;
1302                                 if (si == start + target.Length)
1303                                         return true;
1304                         }
1305
1306                         PreviousInfo prev = new PreviousInfo (false);
1307                         byte* sk1 = stackalloc byte [4];
1308                         byte* sk2 = stackalloc byte [4];
1309                         ClearBuffer (sk1, 4);
1310                         ClearBuffer (sk2, 4);
1311                         return IsSuffix (opt, s, target, start, length, ref prev, sk1, sk2);
1312 */
1313                 }
1314 /*
1315                 unsafe bool IsSuffix (string s, string t, int start, int length, ref Context ctx)
1316                 {
1317                         int tstart = 0;
1318                         COpt opt = ctx.Option;
1319
1320                         for (;tstart < t.Length; tstart++)
1321                                 if (!IsIgnorable (t [tstart], opt))
1322                                         break;
1323                         if (tstart == t.Length)
1324                                 return true; // as if target is String.Empty.
1325
1326 #if false
1327 // This is still not working. If it is not likely to get working, then just remove it.
1328                         int si = start;
1329                         int send = start - length;
1330                         int ti = t.Length - 1;
1331                         int tend = -1;
1332
1333                         int sStep = start + 1;
1334                         int tStep = t.Length;
1335                         bool sourceConsumed, targetConsumed;
1336                         while (true) {
1337                                 for (; send < si; si--)
1338                                         if (!IsIgnorable (s [si]))
1339                                                 break;
1340                                 for (; tend < ti; ti--)
1341                                         if (!IsIgnorable (t [ti]))
1342                                                 break;
1343                                 if (tend == ti)
1344                                         break;
1345                                 for (; send < si; si--)
1346                                         if (IsSafe (s [si]))
1347                                                 break;
1348                                 for (; tend < ti; ti--)
1349                                         if (IsSafe (t [ti]))
1350                                                 break;
1351 Console.WriteLine ("==== {0} {1} {2} {3} {4} {5} {6} {7} {8}", s, si, send, length, t, ti, tstart, sStep - si, tStep - ti);
1352                                 if (CompareInternal (opt, s, si, sStep - si,
1353                                         t, ti, tStep - ti,
1354                                         out targetConsumed, out sourceConsumed,
1355                                         true) != 0)
1356                                         return false;
1357                                 if (send == si)
1358                                         return false;
1359                                 sStep = si;
1360                                 tStep = ti;
1361                                 si--;
1362                                 ti--;
1363                         }
1364                         return true;
1365 #else
1366                         // FIXME: it is not efficient for very long target.
1367                         bool sourceConsumed, targetConsumed;
1368                         int mismatchCount = 0;
1369                         for (int i = 0; i < length; i++) {
1370                                 ctx.ClearPrevInfo ();
1371
1372                                 int ret = CompareInternal (s, start - i, i + 1,
1373                                         t, tstart, t.Length - tstart,
1374                                         out targetConsumed,
1375                                         // FIXME: could immediately breakup
1376                                         out sourceConsumed, true, true, ref ctx);
1377                                 if (ret == 0)
1378                                         return true;
1379                                 if (!sourceConsumed && targetConsumed)
1380                                         return false;
1381                                 if (!targetConsumed) {
1382                                         mismatchCount++;
1383                                         if (mismatchCount > Uni.MaxExpansionLength)
1384                                                 // The largest length of an
1385                                                 // expansion is 3, so if the
1386                                                 // target was not consumed more
1387                                                 // than 3 times, then the tail
1388                                                 // character does not match.
1389                                                 return false;
1390                                 }
1391                         }
1392                         return false;
1393 #endif
1394                 }
1395 */
1396                 #endregion
1397
1398                 #region IndexOf() / LastIndexOf()
1399
1400                 // string
1401
1402                 public int IndexOf (string s, string target, CompareOptions opt)
1403                 {
1404                         return IndexOf (s, target, 0, s.Length, opt);
1405                 }
1406
1407                 int QuickIndexOf (string s, string target, int start, int length, out bool testWasUnable)
1408                 {
1409                         int testedSourcePos = -1, testedTargetPos = -1;
1410
1411                         testWasUnable = true;
1412                         if (target.Length == 0)
1413                                 return 0;
1414                         else if (target.Length > length)
1415                                 return -1;
1416                         testWasUnable = false;
1417
1418                         int end = start + length - target.Length + 1;
1419                         for (int i = start; i < end; i++) {
1420                                 bool no = false;
1421                                 for (int j = 0; j < target.Length; j++) {
1422                                         if (testedTargetPos < j) {
1423                                                 char c = target [j];
1424                                                 if (c == 0 || c >= 0x80) {
1425                                                         testWasUnable = true;
1426                                                         return -1;
1427                                                 }
1428                                                 else
1429                                                         testedTargetPos = j;
1430                                         }
1431                                         if (testedSourcePos < i + j) {
1432                                                 char c = s [i + j];
1433                                                 if (c == 0 || c >= 0x80) {
1434                                                         testWasUnable = true;
1435                                                         return -1;
1436                                                 }
1437                                                 else
1438                                                         testedSourcePos = i + j;
1439                                         }
1440                                         if (s [i + j] != target [j]) {
1441                                                 no = true;
1442                                                 break;
1443                                         }
1444                                 }
1445                                 if (no)
1446                                         continue;
1447                                 return i;
1448                         }
1449                         return -1;
1450                 }
1451
1452                 public unsafe int IndexOf (string s, string target, int start, int length, CompareOptions opt)
1453                 {
1454                         if (opt == CompareOptions.Ordinal)
1455                                 throw new NotSupportedException ("Should not be reached");
1456                         if (opt == CompareOptions.OrdinalIgnoreCase)
1457                                 throw new NotSupportedException ("Should not be reached");
1458                         if (opt == CompareOptions.None) {
1459                                 bool testWasUnable;
1460                                 int ret = QuickIndexOf (s, target, start, length, out testWasUnable);
1461                                 if (!testWasUnable)
1462                                         return ret;
1463                         }
1464
1465                         byte* alwaysMatchFlags = stackalloc byte [16];
1466                         byte* neverMatchFlags = stackalloc byte [16];
1467                         byte* targetSortKey = stackalloc byte [4];
1468                         byte* sk1 = stackalloc byte [4];
1469                         byte* sk2 = stackalloc byte [4];
1470                         ClearBuffer (alwaysMatchFlags, 16);
1471                         ClearBuffer (neverMatchFlags, 16);
1472                         ClearBuffer (targetSortKey, 4);
1473                         ClearBuffer (sk1, 4);
1474                         ClearBuffer (sk2, 4);
1475                         Context ctx = new Context (opt, alwaysMatchFlags, neverMatchFlags, sk1, sk2, null);
1476
1477                         return IndexOf (s, target, start, length,
1478                                 targetSortKey, ref ctx);
1479                 }
1480
1481                 // note that it wouldn't be used since ordinal IndexOf()
1482                 // should be directed to icall.
1483                 int IndexOfOrdinal (string s, string target, int start, int length)
1484                 {
1485                         if (target.Length == 0)
1486                                 return 0;
1487                         else if (target.Length > length)
1488                                 return -1;
1489
1490                         int end = start + length - target.Length + 1;
1491                         for (int i = start; i < end; i++) {
1492                                 bool no = false;
1493                                 for (int j = 0; j < target.Length; j++) {
1494                                         if (s [i + j] != target [j]) {
1495                                                 no = true;
1496                                                 break;
1497                                         }
1498                                 }
1499                                 if (no)
1500                                         continue;
1501                                 return i;
1502                         }
1503                         return -1;
1504                 }
1505
1506                 // char
1507
1508                 public int IndexOf (string s, char target, CompareOptions opt)
1509                 {
1510                         return IndexOf (s, target, 0, s.Length, opt);
1511                 }
1512
1513                 public unsafe int IndexOf (string s, char target, int start, int length, CompareOptions opt)
1514                 {
1515                         if (opt == CompareOptions.Ordinal)
1516                                 throw new NotSupportedException ("Should not be reached");
1517                         if (opt == CompareOptions.OrdinalIgnoreCase)
1518                                 throw new NotSupportedException ("Should not be reached");
1519                         byte* alwaysMatchFlags = stackalloc byte [16];
1520                         byte* neverMatchFlags = stackalloc byte [16];
1521                         byte* targetSortKey = stackalloc byte [4];
1522                         byte* sk1 = stackalloc byte [4];
1523                         byte* sk2 = stackalloc byte [4];
1524                         ClearBuffer (alwaysMatchFlags, 16);
1525                         ClearBuffer (neverMatchFlags, 16);
1526                         ClearBuffer (targetSortKey, 4);
1527                         ClearBuffer (sk1, 4);
1528                         ClearBuffer (sk2, 4);
1529                         Context ctx = new Context (opt, alwaysMatchFlags, neverMatchFlags, sk1, sk2, null);
1530
1531                         // If target is contraction, then use string search.
1532                         Contraction ct = GetContraction (target);
1533                         if (ct != null) {
1534                                 if (ct.Replacement != null)
1535                                         return IndexOf (s, ct.Replacement,
1536                                                 start, length, targetSortKey, ref ctx);
1537                                 else {
1538                                         for (int i = 0; i < ct.SortKey.Length; i++)
1539                                                 sk2 [i] = ct.SortKey [i];
1540                                         return IndexOfSortKey (s, start, length, sk2, char.MinValue, -1, true, ref ctx);
1541                                 }
1542                         } else {
1543                                 int ti = FilterOptions ((int) target, opt);
1544                                 targetSortKey [0] = Category (ti);
1545                                 targetSortKey [1] = Level1 (ti);
1546                                 if ((opt & COpt.IgnoreNonSpace) == 0)
1547                                         targetSortKey [2] =
1548                                                 Level2 (ti, ExtenderType.None);
1549                                 targetSortKey [3] = Uni.Level3 (ti);
1550                                 return IndexOfSortKey (s, start, length,
1551                                         targetSortKey, target, ti,
1552                                         !Uni.HasSpecialWeight ((char) ti), ref ctx);
1553                         }
1554                 }
1555
1556                 // note that it wouldn't be used since ordinal IndexOf()
1557                 // should be directed to icall.
1558                 int IndexOfOrdinal (string s, char target, int start, int length)
1559                 {
1560                         int end = start + length;
1561                         for (int i = start; i < end; i++)
1562                                 if (s [i] == target)
1563                                         return i;
1564                         return -1;
1565                 }
1566
1567                 // Searches target byte[] keydata
1568                 unsafe int IndexOfSortKey (string s, int start, int length, byte* sortkey, char target, int ti, bool noLv4, ref Context ctx)
1569                 {
1570                         int end = start + length;
1571                         int idx = start;
1572
1573                         while (idx < end) {
1574                                 int cur = idx;
1575                                 if (MatchesForward (s, ref idx, end, ti, sortkey, noLv4, ref ctx))
1576                                         return cur;
1577                         }
1578                         return -1;
1579                 }
1580
1581                 // Searches string. Search head character (or keydata when
1582                 // the head is contraction sortkey) and try IsPrefix().
1583                 unsafe int IndexOf (string s, string target, int start, int length, byte* targetSortKey, ref Context ctx)
1584                 {
1585                         COpt opt = ctx.Option;
1586                         int tidx = 0;
1587                         for (; tidx < target.Length; tidx++)
1588                                 if (!IsIgnorable (target [tidx], opt))
1589                                         break;
1590                         if (tidx == target.Length)
1591                                 // FIXME: this is likely a hack. A string that is consists of \0 differs from those of other ignorable characters.
1592                                 return IndexOfOrdinal (target, '\0', 0, target.Length) >= 0 ? IndexOfOrdinal (s, target, start, length) : start;
1593                         Contraction ct = GetContraction (target, tidx, target.Length - tidx);
1594                         string replace = ct != null ? ct.Replacement : null;
1595                         byte* sk = replace == null ? targetSortKey : null;
1596                         bool noLv4 = true;
1597                         char tc = char.MinValue;
1598                         int ti = -1;
1599                         if (ct != null && sk != null) {
1600                                 for (int i = 0; i < ct.SortKey.Length; i++)
1601                                         sk [i] = ct.SortKey [i];
1602                         } else if (sk != null) {
1603                                 tc = target [tidx];
1604                                 ti = FilterOptions (target [tidx], opt);
1605                                 sk [0] = Category (ti);
1606                                 sk [1] = Level1 (ti);
1607                                 if ((opt & COpt.IgnoreNonSpace) == 0)
1608                                         sk [2] = Level2 (ti, ExtenderType.None);
1609                                 sk [3] = Uni.Level3 (ti);
1610                                 noLv4 = !Uni.HasSpecialWeight ((char) ti);
1611                         }
1612                         if (sk != null) {
1613                                 for (tidx++; tidx < target.Length; tidx++) {
1614                                         if (Category (target [tidx]) != 1)
1615                                                 break;
1616                                         if (sk [2] == 0)
1617                                                 sk [2] = 2;
1618                                         sk [2] = (byte) (sk [2] + Level2 (target [tidx], ExtenderType.None));
1619                                 }
1620                         }
1621
1622                         do {
1623                                 int idx = 0;
1624                                 if (replace != null)
1625                                         idx = IndexOf (s, replace, start, length, targetSortKey, ref ctx);
1626                                 else
1627                                         idx = IndexOfSortKey (s, start, length, sk, tc, ti, noLv4, ref ctx);
1628                                 if (idx < 0)
1629                                         return -1;
1630                                 length -= idx - start;
1631                                 start = idx;
1632                                 if (IsPrefix (s, target, start, length, false, ref ctx))
1633                                         return idx;
1634                                 Contraction cts = GetContraction (s, start, length);
1635                                 if (cts != null) {
1636                                         start += cts.Source.Length;
1637                                         length -= cts.Source.Length;
1638                                 } else {
1639                                         start++;
1640                                         length--;
1641                                 }
1642                         } while (length > 0);
1643                         return -1;
1644                 }
1645
1646                 //
1647                 // There are the same number of LastIndexOf() methods as
1648                 // IndexOf() related methods, with the same functionalities
1649                 // for each.
1650                 //
1651
1652                 // string
1653
1654                 public int LastIndexOf (string s, string target, CompareOptions opt)
1655                 {
1656                         return LastIndexOf (s, target, s.Length - 1, s.Length, opt);
1657                 }
1658
1659                 public unsafe int LastIndexOf (string s, string target, int start, int length, CompareOptions opt)
1660                 {
1661                         if (opt == CompareOptions.Ordinal)
1662                                 return LastIndexOfOrdinal (s, target, start, length);
1663                         if (opt == CompareOptions.OrdinalIgnoreCase)
1664                                 throw new NotSupportedException ("Should not be reached");
1665                         byte* alwaysMatchFlags = stackalloc byte [16];
1666                         byte* neverMatchFlags = stackalloc byte [16];
1667                         byte* targetSortKey = stackalloc byte [4];
1668                         byte* sk1 = stackalloc byte [4];
1669                         byte* sk2 = stackalloc byte [4];
1670                         ClearBuffer (alwaysMatchFlags, 16);
1671                         ClearBuffer (neverMatchFlags, 16);
1672                         ClearBuffer (targetSortKey, 4);
1673                         ClearBuffer (sk1, 4);
1674                         ClearBuffer (sk2, 4);
1675                         // For some unknown reason CompareQuick() does not work fine w/ LastIndexOf().
1676                         Context ctx = new Context (opt, alwaysMatchFlags, neverMatchFlags, sk1, sk2, null);
1677                         return LastIndexOf (s, target, start, length,
1678                                 targetSortKey, ref ctx);
1679                 }
1680
1681                 int LastIndexOfOrdinal (string s, string target, int start, int length)
1682                 {
1683                         if (target.Length == 0)
1684                                 return start;
1685                         if (s.Length < target.Length || target.Length > length)
1686                                 return -1;
1687                         int end = start - length + target.Length -1;
1688                         char tail = target [target.Length - 1];
1689                         for (int i = start; i > end;) {
1690                                 if (s [i] != tail) {
1691                                         i--;
1692                                         continue;
1693                                 }
1694                                 int x = i - target.Length + 1;
1695                                 i--;
1696                                 bool mismatch = false;
1697                                 for (int j = target.Length - 2; j >= 0; j--)
1698                                         if (s [x + j] != target [j]) {
1699                                                 mismatch = true;
1700                                                 break;
1701                                         }
1702                                 if (mismatch)
1703                                         continue;
1704                                 return x;
1705                         }
1706                         return -1;
1707                 }
1708
1709                 // char
1710
1711                 public int LastIndexOf (string s, char target, CompareOptions opt)
1712                 {
1713                         return LastIndexOf (s, target, s.Length - 1, s.Length, opt);
1714                 }
1715
1716                 public unsafe int LastIndexOf (string s, char target, int start, int length, CompareOptions opt)
1717                 {
1718                         if (opt == CompareOptions.Ordinal)
1719                                 throw new NotSupportedException ();
1720                         if (opt == CompareOptions.OrdinalIgnoreCase)
1721                                 throw new NotSupportedException ();
1722                         byte* alwaysMatchFlags = stackalloc byte [16];
1723                         byte* neverMatchFlags = stackalloc byte [16];
1724                         byte* targetSortKey = stackalloc byte [4];
1725                         byte* sk1 = stackalloc byte [4];
1726                         byte* sk2 = stackalloc byte [4];
1727                         ClearBuffer (alwaysMatchFlags, 16);
1728                         ClearBuffer (neverMatchFlags, 16);
1729                         ClearBuffer (targetSortKey, 4);
1730                         ClearBuffer (sk1, 4);
1731                         ClearBuffer (sk2, 4);
1732                         Context ctx = new Context (opt, alwaysMatchFlags, neverMatchFlags, sk1, sk2, null);
1733
1734                         // If target is a replacement contraction, then use
1735                         // string search.
1736                         Contraction ct = GetContraction (target);
1737                         if (ct != null) {
1738                                 if (ct.Replacement != null)
1739                                         return LastIndexOf (s,
1740                                                 ct.Replacement, start, length,
1741                                                 targetSortKey, ref ctx);
1742                                 else {
1743                                         for (int bi = 0; bi < ct.SortKey.Length; bi++)
1744                                                 sk2 [bi] = ct.SortKey [bi];
1745                                         return LastIndexOfSortKey (s, start,
1746                                                 start, length, sk2,
1747                                                 -1, true, ref ctx);
1748                                 }
1749                         }
1750                         else {
1751                                 int ti = FilterOptions ((int) target, opt);
1752                                 targetSortKey [0] = Category (ti);
1753                                 targetSortKey [1] = Level1 (ti);
1754                                 if ((opt & COpt.IgnoreNonSpace) == 0)
1755                                         targetSortKey [2] = Level2 (ti, ExtenderType.None);
1756                                 targetSortKey [3] = Uni.Level3 (ti);
1757                                 return LastIndexOfSortKey (s, start, start,
1758                                         length, targetSortKey,
1759                                         ti, !Uni.HasSpecialWeight ((char) ti),
1760                                         ref ctx);
1761                         }
1762                 }
1763
1764                 // Searches target byte[] keydata
1765                 unsafe int LastIndexOfSortKey (string s, int start, int orgStart, int length, byte* sortkey, int ti, bool noLv4, ref Context ctx)
1766                 {
1767                         int end = start - length;
1768                         int idx = start;
1769                         while (idx > end) {
1770                                 int cur = idx;
1771                                 if (MatchesBackward (s, ref idx, end, orgStart,
1772                                         ti, sortkey, noLv4, ref ctx))
1773                                         return cur;
1774                         }
1775                         return -1;
1776                 }
1777
1778                 // Searches string. Search head character (or keydata when
1779                 // the head is contraction sortkey) and try IsPrefix().
1780                 unsafe int LastIndexOf (string s, string target, int start, int length, byte* targetSortKey, ref Context ctx)
1781                 {
1782                         COpt opt = ctx.Option;
1783                         int orgStart = start;
1784                         int tidx = 0;
1785                         for (; tidx < target.Length; tidx++)
1786                                 if (!IsIgnorable (target [tidx], opt))
1787                                         break;
1788                         if (tidx == target.Length)
1789                                 // FIXME: this is likely a hack. A string that is consists of \0 differs from those of other ignorable characters.
1790                                 return IndexOfOrdinal (target, '\0', 0, target.Length) >= 0 ? LastIndexOfOrdinal (s, target, start, length) : start;
1791                         Contraction ct = GetContraction (target, tidx, target.Length - tidx);
1792                         string replace = ct != null ? ct.Replacement : null;
1793                         byte* sk = replace == null ? targetSortKey : null;
1794
1795                         bool noLv4 = true;
1796                         int ti = -1;
1797                         if (ct != null && sk != null) {
1798                                 for (int i = 0; i < ct.SortKey.Length; i++)
1799                                         sk [i] = ct.SortKey [i];
1800                         } else if (sk != null) {
1801                                 ti = FilterOptions (target [tidx], opt);
1802                                 sk [0] = Category (ti);
1803                                 sk [1] = Level1 (ti);
1804                                 if ((opt & COpt.IgnoreNonSpace) == 0)
1805                                         sk [2] = Level2 (ti, ExtenderType.None);
1806                                 sk [3] = Uni.Level3 (ti);
1807                                 noLv4 = !Uni.HasSpecialWeight ((char) ti);
1808                         }
1809                         if (sk != null) {
1810                                 for (tidx++; tidx < target.Length; tidx++) {
1811                                         if (Category (target [tidx]) != 1)
1812                                                 break;
1813                                         if (sk [2] == 0)
1814                                                 sk [2] = 2;
1815                                         sk [2] = (byte) (sk [2] + Level2 (target [tidx], ExtenderType.None));
1816                                 }
1817                         }
1818
1819                         do {
1820                                 int idx = 0;
1821
1822                                 if (replace != null)
1823                                         idx = LastIndexOf (s, replace,
1824                                                 start, length,
1825                                                 targetSortKey, ref ctx);
1826                                 else
1827                                         idx = LastIndexOfSortKey (s, start, orgStart, length, sk, ti, noLv4, ref ctx);
1828                                 if (idx < 0)
1829                                         return -1;
1830                                 length -= start - idx;
1831                                 start = idx;
1832
1833                                 if (IsPrefix (s, target, idx, orgStart - idx + 1, false, ref ctx)) {
1834                                         for (;idx < orgStart; idx++)
1835                                                 if (!IsIgnorable (s [idx], opt))
1836                                                         break;
1837                                         return idx;
1838                                 }
1839                                 Contraction cts = GetContraction (s, idx, orgStart - idx + 1);
1840                                 if (cts != null) {
1841                                         start -= cts.Source.Length;
1842                                         length -= cts.Source.Length;
1843                                 } else {
1844                                         start--;
1845                                         length--;
1846                                 }
1847                         } while (length > 0);
1848                         return -1;
1849                 }
1850
1851                 unsafe bool MatchesForward (string s, ref int idx, int end, int ti, byte* sortkey, bool noLv4, ref Context ctx)
1852                 {
1853                         int si = s [idx];
1854                         if (ctx.AlwaysMatchFlags != null && si < 128 && (ctx.AlwaysMatchFlags [si / 8] & (1 << (si % 8))) != 0)
1855                                 return true;
1856                         if (ctx.NeverMatchFlags != null &&
1857                                         si < 128 &&
1858                                         (ctx.NeverMatchFlags [si / 8] & (1 << (si % 8))) != 0) {
1859                                 idx++;
1860                                 return false;
1861                         }
1862                         ExtenderType ext = GetExtenderType (s [idx]);
1863                         Contraction ct = null;
1864                         if (MatchesForwardCore (s, ref idx, end, ti, sortkey, noLv4, ext, ref ct, ref ctx)) {
1865                                 if (ctx.AlwaysMatchFlags != null && ct == null && ext == ExtenderType.None && si < 128)
1866                                         ctx.AlwaysMatchFlags [si / 8] |= (byte) (1 << (si % 8));
1867                                 return true;
1868                         }
1869                         if (ctx.NeverMatchFlags != null && ct == null && ext == ExtenderType.None && si < 128)
1870                                 ctx.NeverMatchFlags [si / 8] |= (byte) (1 << (si % 8));
1871                         return false;
1872                 }
1873
1874                 unsafe bool MatchesForwardCore (string s, ref int idx, int end, int ti, byte* sortkey, bool noLv4, ExtenderType ext, ref Contraction ct, ref Context ctx)
1875                 {
1876                         COpt opt = ctx.Option;
1877                         byte* charSortKey = ctx.Buffer1;
1878                         bool ignoreNonSpace = (opt & COpt.IgnoreNonSpace) != 0;
1879                         int si = -1;
1880                         if (ext == ExtenderType.None)
1881                                 ct = GetContraction (s, idx, end);
1882                         else if (ctx.PrevCode < 0) {
1883                                 if (ctx.PrevSortKey == null) {
1884                                         idx++;
1885                                         return false;
1886                                 }
1887                                 charSortKey = ctx.PrevSortKey;
1888                         }
1889                         else
1890                                 si = FilterExtender (ctx.PrevCode, ext, opt);
1891                         // if lv4 exists, it never matches contraction
1892                         if (ct != null) {
1893                                 idx += ct.Source.Length;
1894                                 if (!noLv4)
1895                                         return false;
1896                                 if (ct.SortKey != null) {
1897                                         for (int i = 0; i < 4; i++)
1898                                                 charSortKey [i] = sortkey [i];
1899                                         ctx.PrevCode = -1;
1900                                         ctx.PrevSortKey = charSortKey;
1901                                 } else {
1902                                         // Here is the core of LAMESPEC
1903                                         // described at the top of the source.
1904                                         int dummy = 0;
1905                                         return MatchesForward (ct.Replacement, ref dummy,
1906                                                 ct.Replacement.Length, ti, sortkey, noLv4, ref ctx);
1907                                 }
1908                         } else {
1909                                 if (si < 0)
1910                                         si = FilterOptions (s [idx], opt);
1911                                 idx++;
1912                                 charSortKey [0] = Category (si);
1913                                 bool noMatch = false;
1914                                 if (sortkey [0] == charSortKey [0])
1915                                         charSortKey [1] = Level1 (si);
1916                                 else
1917                                         noMatch = true;
1918                                 if (!ignoreNonSpace && sortkey [1] == charSortKey [1])
1919                                         charSortKey [2] = Level2 (si, ext);
1920                                 else if (!ignoreNonSpace)
1921                                         noMatch = true;
1922                                 if (noMatch) {
1923                                         for (; idx < end; idx++) {
1924                                                 if (Category (s [idx]) != 1)
1925                                                         break;
1926                                         }
1927                                         return false;
1928                                 }
1929                                 charSortKey [3] = Uni.Level3 (si);
1930                                 if (charSortKey [0] != 1)
1931                                         ctx.PrevCode = si;
1932                         }
1933                         for (; idx < end; idx++) {
1934                                 if (Category (s [idx]) != 1)
1935                                         break;
1936                                 if (ignoreNonSpace)
1937                                         continue;
1938                                 if (charSortKey [2] == 0)
1939                                                 charSortKey [2] = 2;
1940                                         charSortKey [2] = (byte) (charSortKey [2]
1941                                                 + Level2 (s [idx], ExtenderType.None));
1942                         }
1943
1944                         return MatchesPrimitive (opt, charSortKey, si, ext, sortkey, ti, noLv4);
1945                 }
1946
1947                 unsafe bool MatchesPrimitive (COpt opt, byte* source, int si, ExtenderType ext, byte* target, int ti, bool noLv4)
1948                 {
1949                         bool ignoreNonSpace = (opt & COpt.IgnoreNonSpace) != 0;
1950                         if (source [0] != target [0] ||
1951                                 source [1] != target [1] ||
1952                                 (!ignoreNonSpace && source [2] != target [2]) ||
1953                                 source [3] != target [3])
1954                                 return false;
1955                         if (noLv4 && (si < 0 || !Uni.HasSpecialWeight ((char) si)))
1956                                 return true;
1957                         else if (noLv4)
1958                                 return false;
1959                         // Since target can never be an extender, if the source
1960                         // is an expander and it matters, then they never match.
1961                         if (!ignoreNonSpace && ext == ExtenderType.Conditional)
1962                                 return false;
1963                         if (Uni.IsJapaneseSmallLetter ((char) si) !=
1964                                 Uni.IsJapaneseSmallLetter ((char) ti) ||
1965                                 ToDashTypeValue (ext, opt) !=
1966                                 // FIXME: we will have to specify correct value for target
1967                                 ToDashTypeValue (ExtenderType.None, opt) ||
1968                                 !Uni.IsHiragana ((char) si) !=
1969                                 !Uni.IsHiragana ((char) ti) ||
1970                                 IsHalfKana ((char) si, opt) !=
1971                                 IsHalfKana ((char) ti, opt))
1972                                 return false;
1973                         return true;
1974                 }
1975
1976                 unsafe bool MatchesBackward (string s, ref int idx, int end, int orgStart, int ti, byte* sortkey, bool noLv4, ref Context ctx)
1977                 {
1978                         int si = s [idx];
1979                         if (ctx.AlwaysMatchFlags != null && si < 128 && (ctx.AlwaysMatchFlags [si / 8] & (1 << (si % 8))) != 0)
1980                                 return true;
1981                         if (ctx.NeverMatchFlags != null && si < 128 && (ctx.NeverMatchFlags [si / 8] & (1 << (si % 8))) != 0) {
1982                                 idx--;
1983                                 return false;
1984                         }
1985                         ExtenderType ext = GetExtenderType (s [idx]);
1986                         Contraction ct = null;
1987                         if (MatchesBackwardCore (s, ref idx, end, orgStart, ti, sortkey, noLv4, ext, ref ct, ref ctx)) {
1988                                 if (ctx.AlwaysMatchFlags != null && ct == null && ext == ExtenderType.None && si < 128)
1989                                         ctx.AlwaysMatchFlags [si / 8] |= (byte) (1 << (si % 8));
1990                                 return true;
1991                         }
1992                         if (ctx.NeverMatchFlags != null && ct == null && ext == ExtenderType.None && si < 128) {
1993                                 ctx.NeverMatchFlags [si / 8] |= (byte) (1 << (si % 8));
1994                         }
1995                         return false;
1996                 }
1997
1998                 unsafe bool MatchesBackwardCore (string s, ref int idx, int end, int orgStart, int ti, byte* sortkey, bool noLv4, ExtenderType ext, ref Contraction ct, ref Context ctx)
1999                 {
2000                         COpt opt = ctx.Option;
2001                         byte* charSortKey = ctx.Buffer1;
2002                         bool ignoreNonSpace = (opt & COpt.IgnoreNonSpace) != 0;
2003                         int cur = idx;
2004                         int si = -1;
2005                         // To handle extenders in source, we need to
2006                         // check next _primary_ character.
2007                         if (ext != ExtenderType.None) {
2008                                 byte diacritical = 0;
2009                                 for (int tmp = idx; ; tmp--) {
2010                                         if (tmp < 0) // heading extender
2011                                                 return false;
2012                                         if (IsIgnorable (s [tmp], opt))
2013                                                 continue;
2014                                         int tmpi = FilterOptions (s [tmp], opt);
2015                                         byte category = Category (tmpi);
2016                                         if (category == 1) {
2017                                                 diacritical = Level2 (tmpi, ExtenderType.None);
2018                                                 continue;
2019                                         }
2020                                         si = FilterExtender (tmpi, ext, opt);
2021                                         charSortKey [0] = category;
2022                                         charSortKey [1] = Level1 (si);
2023                                         if (!ignoreNonSpace)
2024                                                 charSortKey [2] = Level2 (si, ext);
2025                                         charSortKey [3] = Uni.Level3 (si);
2026                                         if (ext != ExtenderType.Conditional &&
2027                                                 diacritical != 0)
2028                                                 charSortKey [2] =
2029                                                         (charSortKey [2] == 0) ?
2030                                                         (byte) (diacritical + 2) :
2031                                                         diacritical;
2032                                         break;
2033                                 }
2034                                 idx--;
2035                         }
2036                         if (ext == ExtenderType.None)
2037                                 ct = GetTailContraction (s, idx, end);
2038                         // if lv4 exists, it never matches contraction
2039                         if (ct != null) {
2040                                 idx -= ct.Source.Length;
2041                                 if (!noLv4)
2042                                         return false;
2043                                 if (ct.SortKey != null) {
2044                                         for (int i = 0; i < 4; i++)
2045                                                 charSortKey [i] = sortkey [i];
2046                                         ctx.PrevCode = -1;
2047                                         ctx.PrevSortKey = charSortKey;
2048                                 } else {
2049                                         // Here is the core of LAMESPEC
2050                                         // described at the top of the source.
2051                                         int dummy = ct.Replacement.Length - 1;
2052                                         return 0 <= LastIndexOfSortKey (
2053                                                 ct.Replacement, dummy, dummy,
2054                                                 ct.Replacement.Length, sortkey,
2055                                                 ti, noLv4, ref ctx);
2056                                 }
2057                         } else if (ext == ExtenderType.None) {
2058                                 if (si < 0)
2059                                         si = FilterOptions (s [idx], opt);
2060                                 idx--;
2061                                 bool noMatch = false;
2062                                 charSortKey [0] = Category (si);
2063                                 if (charSortKey [0] == sortkey [0])
2064                                         charSortKey [1] = Level1 (si);
2065                                 else
2066                                         noMatch = true;
2067                                 if (!ignoreNonSpace && charSortKey [1] == sortkey [1])
2068                                         charSortKey [2] = Level2 (si, ext);
2069                                 else if (!ignoreNonSpace)
2070                                         noMatch = true;
2071                                 if (noMatch)
2072                                         return false;
2073                                 charSortKey [3] = Uni.Level3 (si);
2074                                 if (charSortKey [0] != 1)
2075                                         ctx.PrevCode = si;
2076                         }
2077                         if (ext == ExtenderType.None) {
2078                                 for (int tmp = cur + 1; tmp < orgStart; tmp++) {
2079                                         if (Category (s [tmp]) != 1)
2080                                                 break;
2081                                         if (ignoreNonSpace)
2082                                                 continue;
2083                                         if (charSortKey [2] == 0)
2084                                                         charSortKey [2] = 2;
2085                                         charSortKey [2] = (byte) (charSortKey [2]
2086                                                 + Level2 (s [tmp], ExtenderType.None));
2087                                 }
2088                         }
2089                         return MatchesPrimitive (opt, charSortKey, si, ext, sortkey, ti, noLv4);
2090                 }
2091                 #endregion
2092         }
2093 }