1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 // See the LICENSE file in the project root for more information. 4 5 using System.Diagnostics; 6 using System.Runtime.InteropServices; 7 8 namespace System.Globalization 9 { 10 public partial class CompareInfo 11 { InitSort(CultureInfo culture)12 private unsafe void InitSort(CultureInfo culture) 13 { 14 _sortName = culture.SortName; 15 16 if (_invariantMode) 17 { 18 _sortHandle = IntPtr.Zero; 19 } 20 else 21 { 22 const uint LCMAP_SORTHANDLE = 0x20000000; 23 24 IntPtr handle; 25 int ret = Interop.Kernel32.LCMapStringEx(_sortName, LCMAP_SORTHANDLE, null, 0, &handle, IntPtr.Size, null, null, IntPtr.Zero); 26 _sortHandle = ret > 0 ? handle : IntPtr.Zero; 27 } 28 } 29 FindStringOrdinal( uint dwFindStringOrdinalFlags, string stringSource, int offset, int cchSource, string value, int cchValue, bool bIgnoreCase)30 private static unsafe int FindStringOrdinal( 31 uint dwFindStringOrdinalFlags, 32 string stringSource, 33 int offset, 34 int cchSource, 35 string value, 36 int cchValue, 37 bool bIgnoreCase) 38 { 39 Debug.Assert(!GlobalizationMode.Invariant); 40 41 fixed (char* pSource = stringSource) 42 fixed (char* pValue = value) 43 { 44 int ret = Interop.Kernel32.FindStringOrdinal( 45 dwFindStringOrdinalFlags, 46 pSource + offset, 47 cchSource, 48 pValue, 49 cchValue, 50 bIgnoreCase ? 1 : 0); 51 return ret < 0 ? ret : ret + offset; 52 } 53 } 54 IndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)55 internal static int IndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase) 56 { 57 Debug.Assert(!GlobalizationMode.Invariant); 58 59 Debug.Assert(source != null); 60 Debug.Assert(value != null); 61 62 return FindStringOrdinal(FIND_FROMSTART, source, startIndex, count, value, value.Length, ignoreCase); 63 } 64 LastIndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)65 internal static int LastIndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase) 66 { 67 Debug.Assert(!GlobalizationMode.Invariant); 68 69 Debug.Assert(source != null); 70 Debug.Assert(value != null); 71 72 return FindStringOrdinal(FIND_FROMEND, source, startIndex - count + 1, count, value, value.Length, ignoreCase); 73 } 74 GetHashCodeOfStringCore(string source, CompareOptions options)75 private unsafe int GetHashCodeOfStringCore(string source, CompareOptions options) 76 { 77 Debug.Assert(!_invariantMode); 78 79 Debug.Assert(source != null); 80 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0); 81 82 if (source.Length == 0) 83 { 84 return 0; 85 } 86 87 int tmpHash = 0; 88 89 fixed (char* pSource = source) 90 { 91 if (Interop.Kernel32.LCMapStringEx(_sortHandle != IntPtr.Zero ? null : _sortName, 92 LCMAP_HASH | (uint)GetNativeCompareFlags(options), 93 pSource, source.Length, 94 &tmpHash, sizeof(int), 95 null, null, _sortHandle) == 0) 96 { 97 Environment.FailFast("LCMapStringEx failed!"); 98 } 99 } 100 101 return tmpHash; 102 } 103 CompareStringOrdinalIgnoreCase(char* string1, int count1, char* string2, int count2)104 private static unsafe int CompareStringOrdinalIgnoreCase(char* string1, int count1, char* string2, int count2) 105 { 106 Debug.Assert(!GlobalizationMode.Invariant); 107 108 // Use the OS to compare and then convert the result to expected value by subtracting 2 109 return Interop.Kernel32.CompareStringOrdinal(string1, count1, string2, count2, true) - 2; 110 } 111 112 // TODO https://github.com/dotnet/coreclr/issues/13827: 113 // This method shouldn't be necessary, as we should be able to just use the overload 114 // that takes two spans. But due to this issue, that's adding significant overhead. CompareString(ReadOnlySpan<char> string1, string string2, CompareOptions options)115 private unsafe int CompareString(ReadOnlySpan<char> string1, string string2, CompareOptions options) 116 { 117 Debug.Assert(string2 != null); 118 Debug.Assert(!_invariantMode); 119 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0); 120 121 string localeName = _sortHandle != IntPtr.Zero ? null : _sortName; 122 123 fixed (char* pLocaleName = localeName) 124 fixed (char* pString1 = &MemoryMarshal.GetReference(string1)) 125 fixed (char* pString2 = &string2.GetRawStringData()) 126 { 127 int result = Interop.Kernel32.CompareStringEx( 128 pLocaleName, 129 (uint)GetNativeCompareFlags(options), 130 pString1, 131 string1.Length, 132 pString2, 133 string2.Length, 134 null, 135 null, 136 _sortHandle); 137 138 if (result == 0) 139 { 140 Environment.FailFast("CompareStringEx failed"); 141 } 142 143 // Map CompareStringEx return value to -1, 0, 1. 144 return result - 2; 145 } 146 } 147 CompareString(ReadOnlySpan<char> string1, ReadOnlySpan<char> string2, CompareOptions options)148 private unsafe int CompareString(ReadOnlySpan<char> string1, ReadOnlySpan<char> string2, CompareOptions options) 149 { 150 Debug.Assert(!_invariantMode); 151 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0); 152 153 string localeName = _sortHandle != IntPtr.Zero ? null : _sortName; 154 155 fixed (char* pLocaleName = localeName) 156 fixed (char* pString1 = &MemoryMarshal.GetReference(string1)) 157 fixed (char* pString2 = &MemoryMarshal.GetReference(string2)) 158 { 159 int result = Interop.Kernel32.CompareStringEx( 160 pLocaleName, 161 (uint)GetNativeCompareFlags(options), 162 pString1, 163 string1.Length, 164 pString2, 165 string2.Length, 166 null, 167 null, 168 _sortHandle); 169 170 if (result == 0) 171 { 172 Environment.FailFast("CompareStringEx failed"); 173 } 174 175 // Map CompareStringEx return value to -1, 0, 1. 176 return result - 2; 177 } 178 } 179 FindString( uint dwFindNLSStringFlags, string lpStringSource, int startSource, int cchSource, string lpStringValue, int startValue, int cchValue, int* pcchFound)180 private unsafe int FindString( 181 uint dwFindNLSStringFlags, 182 string lpStringSource, 183 int startSource, 184 int cchSource, 185 string lpStringValue, 186 int startValue, 187 int cchValue, 188 int* pcchFound) 189 { 190 Debug.Assert(!_invariantMode); 191 192 string localeName = _sortHandle != IntPtr.Zero ? null : _sortName; 193 194 fixed (char* pLocaleName = localeName) 195 fixed (char* pSource = lpStringSource) 196 fixed (char* pValue = lpStringValue) 197 { 198 char* pS = pSource + startSource; 199 char* pV = pValue + startValue; 200 201 return Interop.Kernel32.FindNLSStringEx( 202 pLocaleName, 203 dwFindNLSStringFlags, 204 pS, 205 cchSource, 206 pV, 207 cchValue, 208 pcchFound, 209 null, 210 null, 211 _sortHandle); 212 } 213 } 214 IndexOfCore(string source, string target, int startIndex, int count, CompareOptions options, int* matchLengthPtr)215 internal unsafe int IndexOfCore(string source, string target, int startIndex, int count, CompareOptions options, int* matchLengthPtr) 216 { 217 Debug.Assert(!string.IsNullOrEmpty(source)); 218 Debug.Assert(target != null); 219 Debug.Assert((options & CompareOptions.OrdinalIgnoreCase) == 0); 220 221 int index; 222 223 // TODO: Consider moving this up to the relevent APIs we need to ensure this behavior for 224 // and add a precondition that target is not empty. 225 if (target.Length == 0) 226 { 227 if(matchLengthPtr != null) 228 *matchLengthPtr = 0; 229 return startIndex; // keep Whidbey compatibility 230 } 231 232 if ((options & CompareOptions.Ordinal) != 0) 233 { 234 index = FastIndexOfString(source, target, startIndex, count, target.Length, findLastIndex: false); 235 if(index != -1 && matchLengthPtr != null) 236 *matchLengthPtr = target.Length; 237 238 return index; 239 } 240 else 241 { 242 int retValue = FindString(FIND_FROMSTART | (uint)GetNativeCompareFlags(options), 243 source, 244 startIndex, 245 count, 246 target, 247 0, 248 target.Length, 249 matchLengthPtr); 250 if (retValue >= 0) 251 { 252 return retValue + startIndex; 253 } 254 } 255 256 return -1; 257 } 258 LastIndexOfCore(string source, string target, int startIndex, int count, CompareOptions options)259 private unsafe int LastIndexOfCore(string source, string target, int startIndex, int count, CompareOptions options) 260 { 261 Debug.Assert(!_invariantMode); 262 263 Debug.Assert(!string.IsNullOrEmpty(source)); 264 Debug.Assert(target != null); 265 Debug.Assert((options & CompareOptions.OrdinalIgnoreCase) == 0); 266 267 // TODO: Consider moving this up to the relevent APIs we need to ensure this behavior for 268 // and add a precondition that target is not empty. 269 if (target.Length == 0) 270 return startIndex; // keep Whidbey compatibility 271 272 if ((options & CompareOptions.Ordinal) != 0) 273 { 274 return FastIndexOfString(source, target, startIndex, count, target.Length, findLastIndex: true); 275 } 276 else 277 { 278 int retValue = FindString(FIND_FROMEND | (uint)GetNativeCompareFlags(options), 279 source, 280 startIndex - count + 1, 281 count, 282 target, 283 0, 284 target.Length, 285 null); 286 287 if (retValue >= 0) 288 { 289 return retValue + startIndex - (count - 1); 290 } 291 } 292 293 return -1; 294 } 295 StartsWith(string source, string prefix, CompareOptions options)296 private unsafe bool StartsWith(string source, string prefix, CompareOptions options) 297 { 298 Debug.Assert(!_invariantMode); 299 300 Debug.Assert(!string.IsNullOrEmpty(source)); 301 Debug.Assert(!string.IsNullOrEmpty(prefix)); 302 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0); 303 304 return FindString(FIND_STARTSWITH | (uint)GetNativeCompareFlags(options), 305 source, 306 0, 307 source.Length, 308 prefix, 309 0, 310 prefix.Length, 311 null) >= 0; 312 } 313 EndsWith(string source, string suffix, CompareOptions options)314 private unsafe bool EndsWith(string source, string suffix, CompareOptions options) 315 { 316 Debug.Assert(!_invariantMode); 317 318 Debug.Assert(!string.IsNullOrEmpty(source)); 319 Debug.Assert(!string.IsNullOrEmpty(suffix)); 320 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0); 321 322 return FindString(FIND_ENDSWITH | (uint)GetNativeCompareFlags(options), 323 source, 324 0, 325 source.Length, 326 suffix, 327 0, 328 suffix.Length, 329 null) >= 0; 330 } 331 332 // PAL ends here 333 [NonSerialized] 334 private IntPtr _sortHandle; 335 336 private const uint LCMAP_SORTKEY = 0x00000400; 337 private const uint LCMAP_HASH = 0x00040000; 338 339 private const int FIND_STARTSWITH = 0x00100000; 340 private const int FIND_ENDSWITH = 0x00200000; 341 private const int FIND_FROMSTART = 0x00400000; 342 private const int FIND_FROMEND = 0x00800000; 343 344 // TODO: Instead of this method could we just have upstack code call IndexOfOrdinal with ignoreCase = false? FastIndexOfString(string source, string target, int startIndex, int sourceCount, int targetCount, bool findLastIndex)345 private static unsafe int FastIndexOfString(string source, string target, int startIndex, int sourceCount, int targetCount, bool findLastIndex) 346 { 347 int retValue = -1; 348 349 int sourceStartIndex = findLastIndex ? startIndex - sourceCount + 1 : startIndex; 350 351 fixed (char* pSource = source, spTarget = target) 352 { 353 char* spSubSource = pSource + sourceStartIndex; 354 355 if (findLastIndex) 356 { 357 int startPattern = (sourceCount - 1) - targetCount + 1; 358 if (startPattern < 0) 359 return -1; 360 361 char patternChar0 = spTarget[0]; 362 for (int ctrSrc = startPattern; ctrSrc >= 0; ctrSrc--) 363 { 364 if (spSubSource[ctrSrc] != patternChar0) 365 continue; 366 367 int ctrPat; 368 for (ctrPat = 1; ctrPat < targetCount; ctrPat++) 369 { 370 if (spSubSource[ctrSrc + ctrPat] != spTarget[ctrPat]) 371 break; 372 } 373 if (ctrPat == targetCount) 374 { 375 retValue = ctrSrc; 376 break; 377 } 378 } 379 380 if (retValue >= 0) 381 { 382 retValue += startIndex - sourceCount + 1; 383 } 384 } 385 else 386 { 387 int endPattern = (sourceCount - 1) - targetCount + 1; 388 if (endPattern < 0) 389 return -1; 390 391 char patternChar0 = spTarget[0]; 392 for (int ctrSrc = 0; ctrSrc <= endPattern; ctrSrc++) 393 { 394 if (spSubSource[ctrSrc] != patternChar0) 395 continue; 396 int ctrPat; 397 for (ctrPat = 1; ctrPat < targetCount; ctrPat++) 398 { 399 if (spSubSource[ctrSrc + ctrPat] != spTarget[ctrPat]) 400 break; 401 } 402 if (ctrPat == targetCount) 403 { 404 retValue = ctrSrc; 405 break; 406 } 407 } 408 409 if (retValue >= 0) 410 { 411 retValue += startIndex; 412 } 413 } 414 } 415 416 return retValue; 417 } 418 CreateSortKey(String source, CompareOptions options)419 private unsafe SortKey CreateSortKey(String source, CompareOptions options) 420 { 421 Debug.Assert(!_invariantMode); 422 423 if (source == null) { throw new ArgumentNullException(nameof(source)); } 424 425 if ((options & ValidSortkeyCtorMaskOffFlags) != 0) 426 { 427 throw new ArgumentException(SR.Argument_InvalidFlag, nameof(options)); 428 } 429 430 byte [] keyData = null; 431 if (source.Length == 0) 432 { 433 keyData = Array.Empty<byte>(); 434 } 435 else 436 { 437 fixed (char *pSource = source) 438 { 439 int result = Interop.Kernel32.LCMapStringEx(_sortHandle != IntPtr.Zero ? null : _sortName, 440 LCMAP_SORTKEY | (uint) GetNativeCompareFlags(options), 441 pSource, source.Length, 442 null, 0, 443 null, null, _sortHandle); 444 if (result == 0) 445 { 446 throw new ArgumentException(SR.Argument_InvalidFlag, "source"); 447 } 448 449 keyData = new byte[result]; 450 451 fixed (byte* pBytes = keyData) 452 { 453 result = Interop.Kernel32.LCMapStringEx(_sortHandle != IntPtr.Zero ? null : _sortName, 454 LCMAP_SORTKEY | (uint) GetNativeCompareFlags(options), 455 pSource, source.Length, 456 pBytes, keyData.Length, 457 null, null, _sortHandle); 458 } 459 } 460 } 461 462 return new SortKey(Name, source, options, keyData); 463 } 464 IsSortable(char* text, int length)465 private static unsafe bool IsSortable(char* text, int length) 466 { 467 Debug.Assert(!GlobalizationMode.Invariant); 468 469 return Interop.Kernel32.IsNLSDefinedString(Interop.Kernel32.COMPARE_STRING, 0, IntPtr.Zero, text, length); 470 } 471 472 private const int COMPARE_OPTIONS_ORDINAL = 0x40000000; // Ordinal 473 private const int NORM_IGNORECASE = 0x00000001; // Ignores case. (use LINGUISTIC_IGNORECASE instead) 474 private const int NORM_IGNOREKANATYPE = 0x00010000; // Does not differentiate between Hiragana and Katakana characters. Corresponding Hiragana and Katakana will compare as equal. 475 private const int NORM_IGNORENONSPACE = 0x00000002; // Ignores nonspacing. This flag also removes Japanese accent characters. (use LINGUISTIC_IGNOREDIACRITIC instead) 476 private const int NORM_IGNORESYMBOLS = 0x00000004; // Ignores symbols. 477 private const int NORM_IGNOREWIDTH = 0x00020000; // Does not differentiate between a single-byte character and the same character as a double-byte character. 478 private const int NORM_LINGUISTIC_CASING = 0x08000000; // use linguistic rules for casing 479 private const int SORT_STRINGSORT = 0x00001000; // Treats punctuation the same as symbols. 480 GetNativeCompareFlags(CompareOptions options)481 private static int GetNativeCompareFlags(CompareOptions options) 482 { 483 // Use "linguistic casing" by default (load the culture's casing exception tables) 484 int nativeCompareFlags = NORM_LINGUISTIC_CASING; 485 486 if ((options & CompareOptions.IgnoreCase) != 0) { nativeCompareFlags |= NORM_IGNORECASE; } 487 if ((options & CompareOptions.IgnoreKanaType) != 0) { nativeCompareFlags |= NORM_IGNOREKANATYPE; } 488 if ((options & CompareOptions.IgnoreNonSpace) != 0) { nativeCompareFlags |= NORM_IGNORENONSPACE; } 489 if ((options & CompareOptions.IgnoreSymbols) != 0) { nativeCompareFlags |= NORM_IGNORESYMBOLS; } 490 if ((options & CompareOptions.IgnoreWidth) != 0) { nativeCompareFlags |= NORM_IGNOREWIDTH; } 491 if ((options & CompareOptions.StringSort) != 0) { nativeCompareFlags |= SORT_STRINGSORT; } 492 493 // TODO: Can we try for GetNativeCompareFlags to never 494 // take Ordinal or OrdinalIgnoreCase. This value is not part of Win32, we just handle it special 495 // in some places. 496 // Suffix & Prefix shouldn't use this, make sure to turn off the NORM_LINGUISTIC_CASING flag 497 if (options == CompareOptions.Ordinal) { nativeCompareFlags = COMPARE_OPTIONS_ORDINAL; } 498 499 Debug.Assert(((options & ~(CompareOptions.IgnoreCase | 500 CompareOptions.IgnoreKanaType | 501 CompareOptions.IgnoreNonSpace | 502 CompareOptions.IgnoreSymbols | 503 CompareOptions.IgnoreWidth | 504 CompareOptions.StringSort)) == 0) || 505 (options == CompareOptions.Ordinal), "[CompareInfo.GetNativeCompareFlags]Expected all flags to be handled"); 506 507 return nativeCompareFlags; 508 } 509 GetSortVersion()510 private unsafe SortVersion GetSortVersion() 511 { 512 Debug.Assert(!_invariantMode); 513 514 Interop.Kernel32.NlsVersionInfoEx nlsVersion = new Interop.Kernel32.NlsVersionInfoEx(); 515 Interop.Kernel32.GetNLSVersionEx(Interop.Kernel32.COMPARE_STRING, _sortName, &nlsVersion); 516 return new SortVersion( 517 nlsVersion.dwNLSVersion, 518 nlsVersion.dwEffectiveId == 0 ? LCID : nlsVersion.dwEffectiveId, 519 nlsVersion.guidCustomVersion); 520 } 521 } 522 } 523