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.
6 using System.Diagnostics;
7 using System.Runtime.CompilerServices;
8 using System.Runtime.InteropServices;
11 namespace System.Globalization
13 public partial class CompareInfo
16 private Interop.Globalization.SafeSortHandle _sortHandle;
19 private bool _isAsciiEqualityOrdinal;
21 private void InitSort(CultureInfo culture)
23 _sortName = culture.SortName;
27 _isAsciiEqualityOrdinal = true;
31 Interop.Globalization.ResultCode resultCode = Interop.Globalization.GetSortHandle(GetNullTerminatedUtf8String(_sortName), out _sortHandle);
32 if (resultCode != Interop.Globalization.ResultCode.Success)
34 _sortHandle.Dispose();
36 if (resultCode == Interop.Globalization.ResultCode.OutOfMemory)
37 throw new OutOfMemoryException();
39 throw new ExternalException(SR.Arg_ExternalException);
41 _isAsciiEqualityOrdinal = (_sortName == "en-US" || _sortName == "");
45 internal static unsafe int IndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)
47 Debug.Assert(!GlobalizationMode.Invariant);
49 Debug.Assert(source != null);
50 Debug.Assert(value != null);
52 if (value.Length == 0)
57 if (count < value.Length)
64 fixed (char* pSource = source)
66 int index = Interop.Globalization.IndexOfOrdinalIgnoreCase(value, value.Length, pSource + startIndex, count, findLast: false);
73 int endIndex = startIndex + (count - value.Length);
74 for (int i = startIndex; i <= endIndex; i++)
76 int valueIndex, sourceIndex;
78 for (valueIndex = 0, sourceIndex = i;
79 valueIndex < value.Length && source[sourceIndex] == value[valueIndex];
80 valueIndex++, sourceIndex++) ;
82 if (valueIndex == value.Length)
91 internal static unsafe int IndexOfOrdinalCore(ReadOnlySpan<char> source, ReadOnlySpan<char> value, bool ignoreCase)
93 Debug.Assert(!GlobalizationMode.Invariant);
95 Debug.Assert(source.Length != 0);
96 Debug.Assert(value.Length != 0);
98 if (source.Length < value.Length)
105 fixed (char* pSource = &MemoryMarshal.GetReference(source))
106 fixed (char* pValue = &MemoryMarshal.GetReference(value))
108 int index = Interop.Globalization.IndexOfOrdinalIgnoreCase(pValue, value.Length, pSource, source.Length, findLast: false);
113 int endIndex = source.Length - value.Length;
114 for (int i = 0; i <= endIndex; i++)
116 int valueIndex, sourceIndex;
118 for (valueIndex = 0, sourceIndex = i;
119 valueIndex < value.Length && source[sourceIndex] == value[valueIndex];
120 valueIndex++, sourceIndex++)
123 if (valueIndex == value.Length)
132 internal static unsafe int LastIndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)
134 Debug.Assert(!GlobalizationMode.Invariant);
136 Debug.Assert(source != null);
137 Debug.Assert(value != null);
139 if (value.Length == 0)
144 if (count < value.Length)
149 // startIndex is the index into source where we start search backwards from.
150 // leftStartIndex is the index into source of the start of the string that is
151 // count characters away from startIndex.
152 int leftStartIndex = startIndex - count + 1;
156 fixed (char* pSource = source)
158 int lastIndex = Interop.Globalization.IndexOfOrdinalIgnoreCase(value, value.Length, pSource + leftStartIndex, count, findLast: true);
159 return lastIndex != -1 ?
160 leftStartIndex + lastIndex :
165 for (int i = startIndex - value.Length + 1; i >= leftStartIndex; i--)
167 int valueIndex, sourceIndex;
169 for (valueIndex = 0, sourceIndex = i;
170 valueIndex < value.Length && source[sourceIndex] == value[valueIndex];
171 valueIndex++, sourceIndex++) ;
173 if (valueIndex == value.Length) {
181 private static unsafe int CompareStringOrdinalIgnoreCase(char* string1, int count1, char* string2, int count2)
183 Debug.Assert(!GlobalizationMode.Invariant);
185 return Interop.Globalization.CompareStringOrdinalIgnoreCase(string1, count1, string2, count2);
188 // TODO https://github.com/dotnet/coreclr/issues/13827:
189 // This method shouldn't be necessary, as we should be able to just use the overload
190 // that takes two spans. But due to this issue, that's adding significant overhead.
191 private unsafe int CompareString(ReadOnlySpan<char> string1, string string2, CompareOptions options)
193 Debug.Assert(!_invariantMode);
194 Debug.Assert(string2 != null);
195 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
197 fixed (char* pString1 = &MemoryMarshal.GetReference(string1))
198 fixed (char* pString2 = &string2.GetRawStringData())
200 return Interop.Globalization.CompareString(_sortHandle, pString1, string1.Length, pString2, string2.Length, options);
204 private unsafe int CompareString(ReadOnlySpan<char> string1, ReadOnlySpan<char> string2, CompareOptions options)
206 Debug.Assert(!_invariantMode);
207 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
209 fixed (char* pString1 = &MemoryMarshal.GetReference(string1))
210 fixed (char* pString2 = &MemoryMarshal.GetReference(string2))
212 return Interop.Globalization.CompareString(_sortHandle, pString1, string1.Length, pString2, string2.Length, options);
216 internal unsafe int IndexOfCore(string source, string target, int startIndex, int count, CompareOptions options, int* matchLengthPtr)
218 Debug.Assert(!_invariantMode);
220 Debug.Assert(!string.IsNullOrEmpty(source));
221 Debug.Assert(target != null);
222 Debug.Assert((options & CompareOptions.OrdinalIgnoreCase) == 0);
226 if (target.Length == 0)
228 if (matchLengthPtr != null)
233 if (options == CompareOptions.Ordinal)
235 index = IndexOfOrdinal(source, target, startIndex, count, ignoreCase: false);
238 if (matchLengthPtr != null)
239 *matchLengthPtr = target.Length;
244 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options) && source.IsFastSort() && target.IsFastSort())
246 index = IndexOf(source, target, startIndex, count, GetOrdinalCompareOptions(options));
249 if (matchLengthPtr != null)
250 *matchLengthPtr = target.Length;
255 fixed (char* pSource = source)
257 index = Interop.Globalization.IndexOf(_sortHandle, target, target.Length, pSource + startIndex, count, options, matchLengthPtr);
259 return index != -1 ? index + startIndex : -1;
263 // For now, this method is only called from Span APIs with either options == CompareOptions.None or CompareOptions.IgnoreCase
264 internal unsafe int IndexOfCore(ReadOnlySpan<char> source, ReadOnlySpan<char> target, CompareOptions options, int* matchLengthPtr)
266 Debug.Assert(!_invariantMode);
267 Debug.Assert(source.Length != 0);
268 Debug.Assert(target.Length != 0);
270 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options))
272 if ((options & CompareOptions.IgnoreCase) == CompareOptions.IgnoreCase)
274 return IndexOfOrdinalIgnoreCaseHelper(source, target, options, matchLengthPtr);
278 return IndexOfOrdinalHelper(source, target, options, matchLengthPtr);
283 fixed (char* pSource = &MemoryMarshal.GetReference(source))
284 fixed (char* pTarget = &MemoryMarshal.GetReference(target))
286 return Interop.Globalization.IndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options, matchLengthPtr);
291 private unsafe int IndexOfOrdinalIgnoreCaseHelper(ReadOnlySpan<char> source, ReadOnlySpan<char> target, CompareOptions options, int* matchLengthPtr)
293 Debug.Assert(!_invariantMode);
295 Debug.Assert(!source.IsEmpty);
296 Debug.Assert(!target.IsEmpty);
297 Debug.Assert(_isAsciiEqualityOrdinal);
299 fixed (char* ap = &MemoryMarshal.GetReference(source))
300 fixed (char* bp = &MemoryMarshal.GetReference(target))
304 int endIndex = source.Length - target.Length;
309 for (int j = 0; j < target.Length; j++)
311 char targetChar = *(b + j);
312 if (targetChar >= 0x80 || s_highCharTable[targetChar])
317 for (; i <= endIndex; i++)
322 for (; targetIndex < target.Length; targetIndex++)
324 char valueChar = *(a + sourceIndex);
325 char targetChar = *(b + targetIndex);
327 if (valueChar == targetChar && valueChar < 0x80 && !s_highCharTable[valueChar])
333 // uppercase both chars - notice that we need just one compare per char
334 if ((uint)(valueChar - 'a') <= ('z' - 'a'))
335 valueChar = (char)(valueChar - 0x20);
336 if ((uint)(targetChar - 'a') <= ('z' - 'a'))
337 targetChar = (char)(targetChar - 0x20);
339 if (valueChar >= 0x80 || s_highCharTable[valueChar])
341 else if (valueChar != targetChar)
346 if (targetIndex == target.Length)
348 if (matchLengthPtr != null)
349 *matchLengthPtr = target.Length;
356 return Interop.Globalization.IndexOf(_sortHandle, b, target.Length, a, source.Length, options, matchLengthPtr);
360 private unsafe int IndexOfOrdinalHelper(ReadOnlySpan<char> source, ReadOnlySpan<char> target, CompareOptions options, int* matchLengthPtr)
362 Debug.Assert(!_invariantMode);
364 Debug.Assert(!source.IsEmpty);
365 Debug.Assert(!target.IsEmpty);
366 Debug.Assert(_isAsciiEqualityOrdinal);
368 fixed (char* ap = &MemoryMarshal.GetReference(source))
369 fixed (char* bp = &MemoryMarshal.GetReference(target))
373 int endIndex = source.Length - target.Length;
378 for (int j = 0; j < target.Length; j++)
380 char targetChar = *(b + j);
381 if (targetChar >= 0x80 || s_highCharTable[targetChar])
386 for (; i <= endIndex; i++)
391 for (; targetIndex < target.Length; targetIndex++)
393 char valueChar = *(a + sourceIndex);
394 char targetChar = *(b + targetIndex);
395 if (valueChar >= 0x80 || s_highCharTable[valueChar])
397 else if (valueChar != targetChar)
402 if (targetIndex == target.Length)
404 if (matchLengthPtr != null)
405 *matchLengthPtr = target.Length;
412 return Interop.Globalization.IndexOf(_sortHandle, b, target.Length, a, source.Length, options, matchLengthPtr);
416 private unsafe int LastIndexOfCore(string source, string target, int startIndex, int count, CompareOptions options)
418 Debug.Assert(!_invariantMode);
420 Debug.Assert(!string.IsNullOrEmpty(source));
421 Debug.Assert(target != null);
422 Debug.Assert((options & CompareOptions.OrdinalIgnoreCase) == 0);
424 if (target.Length == 0)
429 if (options == CompareOptions.Ordinal)
431 return LastIndexOfOrdinalCore(source, target, startIndex, count, ignoreCase: false);
434 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options) && source.IsFastSort() && target.IsFastSort())
436 return LastIndexOf(source, target, startIndex, count, GetOrdinalCompareOptions(options));
439 // startIndex is the index into source where we start search backwards from. leftStartIndex is the index into source
440 // of the start of the string that is count characters away from startIndex.
441 int leftStartIndex = (startIndex - count + 1);
443 fixed (char* pSource = source)
445 int lastIndex = Interop.Globalization.LastIndexOf(_sortHandle, target, target.Length, pSource + (startIndex - count + 1), count, options);
447 return lastIndex != -1 ? lastIndex + leftStartIndex : -1;
451 private bool StartsWith(string source, string prefix, CompareOptions options)
453 Debug.Assert(!_invariantMode);
455 Debug.Assert(!string.IsNullOrEmpty(source));
456 Debug.Assert(!string.IsNullOrEmpty(prefix));
457 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
459 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options) && source.IsFastSort() && prefix.IsFastSort())
461 return IsPrefix(source, prefix, GetOrdinalCompareOptions(options));
464 return Interop.Globalization.StartsWith(_sortHandle, prefix, prefix.Length, source, source.Length, options);
467 private unsafe bool StartsWith(ReadOnlySpan<char> source, ReadOnlySpan<char> prefix, CompareOptions options)
469 Debug.Assert(!_invariantMode);
471 Debug.Assert(!source.IsEmpty);
472 Debug.Assert(!prefix.IsEmpty);
473 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
475 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options))
477 if (source.Length < prefix.Length)
482 if ((options & CompareOptions.IgnoreCase) == CompareOptions.IgnoreCase)
484 return StartsWithOrdinalIgnoreCaseHelper(source, prefix, options);
488 return StartsWithOrdinalHelper(source, prefix, options);
493 fixed (char* pSource = &MemoryMarshal.GetReference(source))
494 fixed (char* pPrefix = &MemoryMarshal.GetReference(prefix))
496 return Interop.Globalization.StartsWith(_sortHandle, pPrefix, prefix.Length, pSource, source.Length, options);
501 private unsafe bool StartsWithOrdinalIgnoreCaseHelper(ReadOnlySpan<char> source, ReadOnlySpan<char> prefix, CompareOptions options)
503 Debug.Assert(!_invariantMode);
505 Debug.Assert(!source.IsEmpty);
506 Debug.Assert(!prefix.IsEmpty);
507 Debug.Assert(_isAsciiEqualityOrdinal);
508 Debug.Assert(source.Length >= prefix.Length);
510 int length = prefix.Length;
512 fixed (char* ap = &MemoryMarshal.GetReference(source))
513 fixed (char* bp = &MemoryMarshal.GetReference(prefix))
518 while (length != 0 && (*a < 0x80) && (*b < 0x80) && (!s_highCharTable[*a]) && (!s_highCharTable[*b]))
530 // uppercase both chars - notice that we need just one compare per char
531 if ((uint)(charA - 'a') <= (uint)('z' - 'a')) charA -= 0x20;
532 if ((uint)(charB - 'a') <= (uint)('z' - 'a')) charB -= 0x20;
542 if (length == 0) return true;
543 return Interop.Globalization.StartsWith(_sortHandle, b, length, a, length, options);
547 private unsafe bool StartsWithOrdinalHelper(ReadOnlySpan<char> source, ReadOnlySpan<char> prefix, CompareOptions options)
549 Debug.Assert(!_invariantMode);
551 Debug.Assert(!source.IsEmpty);
552 Debug.Assert(!prefix.IsEmpty);
553 Debug.Assert(_isAsciiEqualityOrdinal);
554 Debug.Assert(source.Length >= prefix.Length);
556 int length = prefix.Length;
558 fixed (char* ap = &MemoryMarshal.GetReference(source))
559 fixed (char* bp = &MemoryMarshal.GetReference(prefix))
564 while (length != 0 && (*a < 0x80) && (*b < 0x80) && (!s_highCharTable[*a]) && (!s_highCharTable[*b]))
577 if (length == 0) return true;
578 return Interop.Globalization.StartsWith(_sortHandle, b, length, a, length, options);
582 private bool EndsWith(string source, string suffix, CompareOptions options)
584 Debug.Assert(!_invariantMode);
586 Debug.Assert(!string.IsNullOrEmpty(source));
587 Debug.Assert(!string.IsNullOrEmpty(suffix));
588 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
590 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options) && source.IsFastSort() && suffix.IsFastSort())
592 return IsSuffix(source, suffix, GetOrdinalCompareOptions(options));
595 return Interop.Globalization.EndsWith(_sortHandle, suffix, suffix.Length, source, source.Length, options);
598 private unsafe bool EndsWith(ReadOnlySpan<char> source, ReadOnlySpan<char> suffix, CompareOptions options)
600 Debug.Assert(!_invariantMode);
602 Debug.Assert(!source.IsEmpty);
603 Debug.Assert(!suffix.IsEmpty);
604 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
606 if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options))
608 if (source.Length < suffix.Length)
613 if ((options & CompareOptions.IgnoreCase) == CompareOptions.IgnoreCase)
615 return EndsWithOrdinalIgnoreCaseHelper(source, suffix, options);
619 return EndsWithOrdinalHelper(source, suffix, options);
624 fixed (char* pSource = &MemoryMarshal.GetReference(source))
625 fixed (char* pSuffix = &MemoryMarshal.GetReference(suffix))
627 return Interop.Globalization.EndsWith(_sortHandle, pSuffix, suffix.Length, pSource, source.Length, options);
632 private unsafe bool EndsWithOrdinalIgnoreCaseHelper(ReadOnlySpan<char> source, ReadOnlySpan<char> suffix, CompareOptions options)
634 Debug.Assert(!_invariantMode);
636 Debug.Assert(!source.IsEmpty);
637 Debug.Assert(!suffix.IsEmpty);
638 Debug.Assert(_isAsciiEqualityOrdinal);
639 Debug.Assert(source.Length >= suffix.Length);
641 int length = suffix.Length;
643 fixed (char* ap = &MemoryMarshal.GetReference(source))
644 fixed (char* bp = &MemoryMarshal.GetReference(suffix))
646 char* a = ap + source.Length - 1;
647 char* b = bp + suffix.Length - 1;
649 while (length != 0 && (*a < 0x80) && (*b < 0x80) && (!s_highCharTable[*a]) && (!s_highCharTable[*b]))
661 // uppercase both chars - notice that we need just one compare per char
662 if ((uint)(charA - 'a') <= (uint)('z' - 'a')) charA -= 0x20;
663 if ((uint)(charB - 'a') <= (uint)('z' - 'a')) charB -= 0x20;
673 if (length == 0) return true;
674 return Interop.Globalization.EndsWith(_sortHandle, b - length + 1, length, a - length + 1, length, options);
678 private unsafe bool EndsWithOrdinalHelper(ReadOnlySpan<char> source, ReadOnlySpan<char> suffix, CompareOptions options)
680 Debug.Assert(!_invariantMode);
682 Debug.Assert(!source.IsEmpty);
683 Debug.Assert(!suffix.IsEmpty);
684 Debug.Assert(_isAsciiEqualityOrdinal);
685 Debug.Assert(source.Length >= suffix.Length);
687 int length = suffix.Length;
689 fixed (char* ap = &MemoryMarshal.GetReference(source))
690 fixed (char* bp = &MemoryMarshal.GetReference(suffix))
692 char* a = ap + source.Length - 1;
693 char* b = bp + suffix.Length - 1;
695 while (length != 0 && (*a < 0x80) && (*b < 0x80) && (!s_highCharTable[*a]) && (!s_highCharTable[*b]))
708 if (length == 0) return true;
709 return Interop.Globalization.EndsWith(_sortHandle, b - length + 1, length, a - length + 1, length, options);
713 private unsafe SortKey CreateSortKey(String source, CompareOptions options)
715 Debug.Assert(!_invariantMode);
717 if (source==null) { throw new ArgumentNullException(nameof(source)); }
719 if ((options & ValidSortkeyCtorMaskOffFlags) != 0)
721 throw new ArgumentException(SR.Argument_InvalidFlag, nameof(options));
725 if (source.Length == 0)
727 keyData = Array.Empty<Byte>();
731 int sortKeyLength = Interop.Globalization.GetSortKey(_sortHandle, source, source.Length, null, 0, options);
732 keyData = new byte[sortKeyLength];
734 fixed (byte* pSortKey = keyData)
736 if (Interop.Globalization.GetSortKey(_sortHandle, source, source.Length, pSortKey, sortKeyLength, options) != sortKeyLength)
738 throw new ArgumentException(SR.Arg_ExternalException);
743 return new SortKey(Name, source, options, keyData);
746 private static unsafe bool IsSortable(char *text, int length)
748 Debug.Assert(!GlobalizationMode.Invariant);
753 while (index < length)
755 if (Char.IsHighSurrogate(text[index]))
757 if (index == length - 1 || !Char.IsLowSurrogate(text[index+1]))
758 return false; // unpaired surrogate
760 uc = CharUnicodeInfo.GetUnicodeCategory(Char.ConvertToUtf32(text[index], text[index+1]));
761 if (uc == UnicodeCategory.PrivateUse || uc == UnicodeCategory.OtherNotAssigned)
768 if (Char.IsLowSurrogate(text[index]))
770 return false; // unpaired surrogate
773 uc = CharUnicodeInfo.GetUnicodeCategory(text[index]);
774 if (uc == UnicodeCategory.PrivateUse || uc == UnicodeCategory.OtherNotAssigned)
785 // -----------------------------
786 // ---- PAL layer ends here ----
787 // -----------------------------
789 internal unsafe int GetHashCodeOfStringCore(string source, CompareOptions options)
791 Debug.Assert(!_invariantMode);
793 Debug.Assert(source != null);
794 Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
796 if (source.Length == 0)
801 int sortKeyLength = Interop.Globalization.GetSortKey(_sortHandle, source, source.Length, null, 0, options);
803 byte[] borrowedArr = null;
804 Span<byte> span = sortKeyLength <= 512 ?
805 stackalloc byte[512] :
806 (borrowedArr = ArrayPool<byte>.Shared.Rent(sortKeyLength));
808 fixed (byte* pSortKey = &MemoryMarshal.GetReference(span))
810 if (Interop.Globalization.GetSortKey(_sortHandle, source, source.Length, pSortKey, sortKeyLength, options) != sortKeyLength)
812 throw new ArgumentException(SR.Arg_ExternalException);
816 int hash = Marvin.ComputeHash32(span.Slice(0, sortKeyLength), Marvin.DefaultSeed);
818 // Return the borrowed array if necessary.
819 if (borrowedArr != null)
821 ArrayPool<byte>.Shared.Return(borrowedArr);
827 private static CompareOptions GetOrdinalCompareOptions(CompareOptions options)
829 if ((options & CompareOptions.IgnoreCase) == CompareOptions.IgnoreCase)
831 return CompareOptions.OrdinalIgnoreCase;
835 return CompareOptions.Ordinal;
839 private static bool CanUseAsciiOrdinalForOptions(CompareOptions options)
841 // Unlike the other Ignore options, IgnoreSymbols impacts ASCII characters (e.g. ').
842 return (options & CompareOptions.IgnoreSymbols) == 0;
845 private static byte[] GetNullTerminatedUtf8String(string s)
847 int byteLen = System.Text.Encoding.UTF8.GetByteCount(s);
849 // Allocate an extra byte (which defaults to 0) as the null terminator.
850 byte[] buffer = new byte[byteLen + 1];
852 int bytesWritten = System.Text.Encoding.UTF8.GetBytes(s, 0, s.Length, buffer, 0);
854 Debug.Assert(bytesWritten == byteLen);
859 private SortVersion GetSortVersion()
861 Debug.Assert(!_invariantMode);
863 int sortVersion = Interop.Globalization.GetSortVersion(_sortHandle);
864 return new SortVersion(sortVersion, LCID, new Guid(sortVersion, 0, 0, 0, 0, 0, 0,
866 (byte) ((LCID & 0x00FF0000) >> 16),
867 (byte) ((LCID & 0x0000FF00) >> 8),
868 (byte) (LCID & 0xFF)));
871 // See https://github.com/dotnet/coreclr/blob/master/src/utilcode/util_nodependencies.cpp#L970
872 private static readonly bool[] s_highCharTable = new bool[0x80]