From 4e645b1a24a9a6eeb5c9944ebbe1dd07ef6228e0 Mon Sep 17 00:00:00 2001 From: Viktor Hofer Date: Wed, 4 Jul 2018 20:56:25 +0200 Subject: [PATCH] Add LastIndexOf compareoptions overload (#18652) * Add LastIndexOf compareoptions overload --- .../Interop.Collation.cs | 4 +- .../System/Globalization/CompareInfo.Invariant.cs | 14 +-- .../System/Globalization/CompareInfo.Unix.cs | 132 +++++++++++++++------ .../System/Globalization/CompareInfo.Windows.cs | 11 +- .../shared/System/Globalization/CompareInfo.cs | 20 +++- .../shared/System/MemoryExtensions.Fast.cs | 46 ++++++- 6 files changed, 169 insertions(+), 58 deletions(-) diff --git a/src/System.Private.CoreLib/shared/Interop/Unix/System.Globalization.Native/Interop.Collation.cs b/src/System.Private.CoreLib/shared/Interop/Unix/System.Globalization.Native/Interop.Collation.cs index 9942882..aeeb60f 100644 --- a/src/System.Private.CoreLib/shared/Interop/Unix/System.Globalization.Native/Interop.Collation.cs +++ b/src/System.Private.CoreLib/shared/Interop/Unix/System.Globalization.Native/Interop.Collation.cs @@ -21,12 +21,10 @@ internal static partial class Interop internal static extern unsafe int CompareString(SafeSortHandle sortHandle, char* lpStr1, int cwStr1Len, char* lpStr2, int cwStr2Len, CompareOptions options); [DllImport(Libraries.GlobalizationNative, CharSet = CharSet.Unicode, EntryPoint = "GlobalizationNative_IndexOf")] - internal static extern unsafe int IndexOf(SafeSortHandle sortHandle, string target, int cwTargetLength, char* pSource, int cwSourceLength, CompareOptions options, int* matchLengthPtr); - [DllImport(Libraries.GlobalizationNative, CharSet = CharSet.Unicode, EntryPoint = "GlobalizationNative_IndexOf")] internal static extern unsafe int IndexOf(SafeSortHandle sortHandle, char* target, int cwTargetLength, char* pSource, int cwSourceLength, CompareOptions options, int* matchLengthPtr); [DllImport(Libraries.GlobalizationNative, CharSet = CharSet.Unicode, EntryPoint = "GlobalizationNative_LastIndexOf")] - internal static extern unsafe int LastIndexOf(SafeSortHandle sortHandle, string target, int cwTargetLength, char* pSource, int cwSourceLength, CompareOptions options); + internal static extern unsafe int LastIndexOf(SafeSortHandle sortHandle, char* target, int cwTargetLength, char* pSource, int cwSourceLength, CompareOptions options); [DllImport(Libraries.GlobalizationNative, CharSet = CharSet.Unicode, EntryPoint = "GlobalizationNative_IndexOfOrdinalIgnoreCase")] internal static extern unsafe int IndexOfOrdinalIgnoreCase(string target, int cwTargetLength, char* pSource, int cwSourceLength, bool findLast); diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Invariant.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Invariant.cs index 29e4f53..16201b8 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Invariant.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Invariant.cs @@ -18,7 +18,7 @@ namespace System.Globalization fixed (char* pSource = source) fixed (char* pValue = value) { char* pSrc = &pSource[startIndex]; - int index = InvariantFindString(pSrc, count, pValue, value.Length, ignoreCase, start : true); + int index = InvariantFindString(pSrc, count, pValue, value.Length, ignoreCase, fromBeginning : true); if (index >= 0) { return index + startIndex; @@ -27,7 +27,7 @@ namespace System.Globalization } } - internal static unsafe int InvariantIndexOf(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase) + internal static unsafe int InvariantIndexOf(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase, bool fromBeginning = true) { Debug.Assert(source.Length != 0); Debug.Assert(value.Length != 0); @@ -35,7 +35,7 @@ namespace System.Globalization fixed (char* pSource = &MemoryMarshal.GetReference(source)) fixed (char* pValue = &MemoryMarshal.GetReference(value)) { - return InvariantFindString(pSource, source.Length, pValue, value.Length, ignoreCase, start: true); + return InvariantFindString(pSource, source.Length, pValue, value.Length, ignoreCase, fromBeginning); } } @@ -48,7 +48,7 @@ namespace System.Globalization fixed (char* pSource = source) fixed (char* pValue = value) { char* pSrc = &pSource[startIndex - count + 1]; - int index = InvariantFindString(pSrc, count, pValue, value.Length, ignoreCase, start : false); + int index = InvariantFindString(pSrc, count, pValue, value.Length, ignoreCase, fromBeginning : false); if (index >= 0) { return index + startIndex - count + 1; @@ -57,7 +57,7 @@ namespace System.Globalization } } - private static unsafe int InvariantFindString(char* source, int sourceCount, char* value, int valueCount, bool ignoreCase, bool start) + private static unsafe int InvariantFindString(char* source, int sourceCount, char* value, int valueCount, bool ignoreCase, bool fromBeginning) { int ctrSource = 0; // index value into source int ctrValue = 0; // index value into value @@ -72,7 +72,7 @@ namespace System.Globalization if (valueCount == 0) { - return start ? 0 : sourceCount - 1; + return fromBeginning ? 0 : sourceCount - 1; } if (sourceCount < valueCount) @@ -80,7 +80,7 @@ namespace System.Globalization return -1; } - if (start) + if (fromBeginning) { lastSourceStart = sourceCount - valueCount; if (ignoreCase) diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs index 90e9eba..f517540 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs @@ -88,7 +88,7 @@ namespace System.Globalization return -1; } - internal static unsafe int IndexOfOrdinalCore(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase) + internal static unsafe int IndexOfOrdinalCore(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase, bool fromBeginning) { Debug.Assert(!GlobalizationMode.Invariant); @@ -105,13 +105,29 @@ namespace System.Globalization fixed (char* pSource = &MemoryMarshal.GetReference(source)) fixed (char* pValue = &MemoryMarshal.GetReference(value)) { - int index = Interop.Globalization.IndexOfOrdinalIgnoreCase(pValue, value.Length, pSource, source.Length, findLast: false); - return index; + return Interop.Globalization.IndexOfOrdinalIgnoreCase(pValue, value.Length, pSource, source.Length, findLast: !fromBeginning); } } - int endIndex = source.Length - value.Length; - for (int i = 0; i <= endIndex; i++) + int startIndex, endIndex, jump; + if (fromBeginning) + { + // Left to right, from zero to last possible index in the source string. + // Incrementing by one after each iteration. Stop condition is last possible index plus 1. + startIndex = 0; + endIndex = source.Length - value.Length + 1; + jump = 1; + } + else + { + // Right to left, from first possible index in the source string to zero. + // Decrementing by one after each iteration. Stop condition is last possible index minus 1. + startIndex = source.Length - value.Length; + endIndex = -1; + jump = -1; + } + + for (int i = startIndex; i != endIndex; i += jump) { int valueIndex, sourceIndex; @@ -259,15 +275,16 @@ namespace System.Globalization #endif fixed (char* pSource = source) + fixed (char* pTarget = target) { - index = Interop.Globalization.IndexOf(_sortHandle, target, target.Length, pSource + startIndex, count, options, matchLengthPtr); + index = Interop.Globalization.IndexOf(_sortHandle, pTarget, target.Length, pSource + startIndex, count, options, matchLengthPtr); return index != -1 ? index + startIndex : -1; } } // For now, this method is only called from Span APIs with either options == CompareOptions.None or CompareOptions.IgnoreCase - internal unsafe int IndexOfCore(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr) + internal unsafe int IndexOfCore(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr, bool fromBeginning) { Debug.Assert(!_invariantMode); Debug.Assert(source.Length != 0); @@ -276,25 +293,29 @@ namespace System.Globalization if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options)) { if ((options & CompareOptions.IgnoreCase) == CompareOptions.IgnoreCase) - { - return IndexOfOrdinalIgnoreCaseHelper(source, target, options, matchLengthPtr); - } + return IndexOfOrdinalIgnoreCaseHelper(source, target, options, matchLengthPtr, fromBeginning); else - { - return IndexOfOrdinalHelper(source, target, options, matchLengthPtr); - } + return IndexOfOrdinalHelper(source, target, options, matchLengthPtr, fromBeginning); } else { fixed (char* pSource = &MemoryMarshal.GetReference(source)) fixed (char* pTarget = &MemoryMarshal.GetReference(target)) { - return Interop.Globalization.IndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options, matchLengthPtr); + if (fromBeginning) + return Interop.Globalization.IndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options, matchLengthPtr); + else + return Interop.Globalization.LastIndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options); } } } - private unsafe int IndexOfOrdinalIgnoreCaseHelper(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr) + /// + /// Duplicate of IndexOfOrdinalHelper that also handles ignore case. Can't converge both methods + /// as the JIT wouldn't be able to optimize the ignoreCase path away. + /// + /// + private unsafe int IndexOfOrdinalIgnoreCaseHelper(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr, bool fromBeginning) { Debug.Assert(!_invariantMode); @@ -307,9 +328,8 @@ namespace System.Globalization { char* a = ap; char* b = bp; - int endIndex = source.Length - target.Length; - if (endIndex < 0) + if (target.Length > source.Length) goto InteropCall; for (int j = 0; j < target.Length; j++) @@ -319,20 +339,36 @@ namespace System.Globalization goto InteropCall; } - int i = 0; - for (; i <= endIndex; i++) + int startIndex, endIndex, jump; + if (fromBeginning) + { + // Left to right, from zero to last possible index in the source string. + // Incrementing by one after each iteration. Stop condition is last possible index plus 1. + startIndex = 0; + endIndex = source.Length - target.Length + 1; + jump = 1; + } + else + { + // Right to left, from first possible index in the source string to zero. + // Decrementing by one after each iteration. Stop condition is last possible index minus 1. + startIndex = source.Length - target.Length; + endIndex = -1; + jump = -1; + } + + for (int i = startIndex; i != endIndex; i += jump) { int targetIndex = 0; int sourceIndex = i; - for (; targetIndex < target.Length; targetIndex++) + for (; targetIndex < target.Length; targetIndex++, sourceIndex++) { char valueChar = *(a + sourceIndex); char targetChar = *(b + targetIndex); if (valueChar == targetChar && valueChar < 0x80 && !s_highCharTable[valueChar]) { - sourceIndex++; continue; } @@ -346,7 +382,6 @@ namespace System.Globalization goto InteropCall; else if (valueChar != targetChar) break; - sourceIndex++; } if (targetIndex == target.Length) @@ -356,14 +391,17 @@ namespace System.Globalization return i; } } - if (i > endIndex) - return -1; - InteropCall: - return Interop.Globalization.IndexOf(_sortHandle, b, target.Length, a, source.Length, options, matchLengthPtr); + + return -1; + InteropCall: + if (fromBeginning) + return Interop.Globalization.IndexOf(_sortHandle, b, target.Length, a, source.Length, options, matchLengthPtr); + else + return Interop.Globalization.LastIndexOf(_sortHandle, b, target.Length, a, source.Length, options); } } - private unsafe int IndexOfOrdinalHelper(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr) + private unsafe int IndexOfOrdinalHelper(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr, bool fromBeginning) { Debug.Assert(!_invariantMode); @@ -376,9 +414,8 @@ namespace System.Globalization { char* a = ap; char* b = bp; - int endIndex = source.Length - target.Length; - if (endIndex < 0) + if (target.Length > source.Length) goto InteropCall; for (int j = 0; j < target.Length; j++) @@ -388,21 +425,38 @@ namespace System.Globalization goto InteropCall; } - int i = 0; - for (; i <= endIndex; i++) + int startIndex, endIndex, jump; + if (fromBeginning) + { + // Left to right, from zero to last possible index in the source string. + // Incrementing by one after each iteration. Stop condition is last possible index plus 1. + startIndex = 0; + endIndex = source.Length - target.Length + 1; + jump = 1; + } + else + { + // Right to left, from first possible index in the source string to zero. + // Decrementing by one after each iteration. Stop condition is last possible index minus 1. + startIndex = source.Length - target.Length; + endIndex = -1; + jump = -1; + } + + for (int i = startIndex; i != endIndex; i += jump) { int targetIndex = 0; int sourceIndex = i; - for (; targetIndex < target.Length; targetIndex++) + for (; targetIndex < target.Length; targetIndex++, sourceIndex++) { char valueChar = *(a + sourceIndex); char targetChar = *(b + targetIndex); + if (valueChar >= 0x80 || s_highCharTable[valueChar]) goto InteropCall; else if (valueChar != targetChar) break; - sourceIndex++; } if (targetIndex == target.Length) @@ -412,10 +466,13 @@ namespace System.Globalization return i; } } - if (i > endIndex) - return -1; + + return -1; InteropCall: - return Interop.Globalization.IndexOf(_sortHandle, b, target.Length, a, source.Length, options, matchLengthPtr); + if (fromBeginning) + return Interop.Globalization.IndexOf(_sortHandle, b, target.Length, a, source.Length, options, matchLengthPtr); + else + return Interop.Globalization.LastIndexOf(_sortHandle, b, target.Length, a, source.Length, options); } } @@ -449,8 +506,9 @@ namespace System.Globalization int leftStartIndex = (startIndex - count + 1); fixed (char* pSource = source) + fixed (char* pTarget = target) { - int lastIndex = Interop.Globalization.LastIndexOf(_sortHandle, target, target.Length, pSource + (startIndex - count + 1), count, options); + int lastIndex = Interop.Globalization.LastIndexOf(_sortHandle, pTarget, target.Length, pSource + (startIndex - count + 1), count, options); return lastIndex != -1 ? lastIndex + leftStartIndex : -1; } diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Windows.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Windows.cs index 2a14e26..d1b12c6 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Windows.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Windows.cs @@ -91,14 +91,15 @@ namespace System.Globalization return FindStringOrdinal(FIND_FROMSTART, source, startIndex, count, value, value.Length, ignoreCase); } - internal static int IndexOfOrdinalCore(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase) + internal static int IndexOfOrdinalCore(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase, bool fromBeginning) { Debug.Assert(!GlobalizationMode.Invariant); Debug.Assert(source.Length != 0); Debug.Assert(value.Length != 0); - return FindStringOrdinal(FIND_FROMSTART, source, value, ignoreCase); + uint positionFlag = fromBeginning ? (uint)FIND_FROMSTART : FIND_FROMEND; + return FindStringOrdinal(positionFlag, source, value, ignoreCase); } internal static int LastIndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase) @@ -359,7 +360,7 @@ namespace System.Globalization return -1; } - internal unsafe int IndexOfCore(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr) + internal unsafe int IndexOfCore(ReadOnlySpan source, ReadOnlySpan target, CompareOptions options, int* matchLengthPtr, bool fromBeginning) { Debug.Assert(!_invariantMode); @@ -367,8 +368,8 @@ namespace System.Globalization Debug.Assert(target.Length != 0); Debug.Assert((options == CompareOptions.None || options == CompareOptions.IgnoreCase)); - int retValue = FindString(FIND_FROMSTART | (uint)GetNativeCompareFlags(options), source, target, matchLengthPtr); - return retValue; + uint positionFlag = fromBeginning ? (uint)FIND_FROMSTART : FIND_FROMEND; + return FindString(positionFlag | (uint)GetNativeCompareFlags(options), source, target, matchLengthPtr); } private unsafe int LastIndexOfCore(string source, string target, int startIndex, int count, CompareOptions options) diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs index 74924ee..92742c7 100644 --- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs +++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.cs @@ -939,7 +939,15 @@ namespace System.Globalization Debug.Assert(!_invariantMode); Debug.Assert(!source.IsEmpty); Debug.Assert(!value.IsEmpty); - return IndexOfOrdinalCore(source, value, ignoreCase); + return IndexOfOrdinalCore(source, value, ignoreCase, fromBeginning: true); + } + + internal int LastIndexOfOrdinal(ReadOnlySpan source, ReadOnlySpan value, bool ignoreCase) + { + Debug.Assert(!_invariantMode); + Debug.Assert(!source.IsEmpty); + Debug.Assert(!value.IsEmpty); + return IndexOfOrdinalCore(source, value, ignoreCase, fromBeginning: false); } internal unsafe int IndexOf(ReadOnlySpan source, ReadOnlySpan value, CompareOptions options) @@ -947,7 +955,15 @@ namespace System.Globalization Debug.Assert(!_invariantMode); Debug.Assert(!source.IsEmpty); Debug.Assert(!value.IsEmpty); - return IndexOfCore(source, value, options, null); + return IndexOfCore(source, value, options, null, fromBeginning: true); + } + + internal unsafe int LastIndexOf(ReadOnlySpan source, ReadOnlySpan value, CompareOptions options) + { + Debug.Assert(!_invariantMode); + Debug.Assert(!source.IsEmpty); + Debug.Assert(!value.IsEmpty); + return IndexOfCore(source, value, options, null, fromBeginning: false); } // The following IndexOf overload is mainly used by String.Replace. This overload assumes the parameters are already validated diff --git a/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs b/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs index f957e6d..a53ed19 100644 --- a/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs +++ b/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs @@ -170,13 +170,51 @@ namespace System case StringComparison.InvariantCultureIgnoreCase: return CompareInfo.Invariant.IndexOf(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType)); - case StringComparison.Ordinal: - case StringComparison.OrdinalIgnoreCase: + default: + Debug.Assert(comparisonType == StringComparison.Ordinal || comparisonType == StringComparison.OrdinalIgnoreCase); return CompareInfo.Invariant.IndexOfOrdinal(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType) != CompareOptions.None); } + } - Debug.Fail("StringComparison outside range"); - return -1; + /// + /// Reports the zero-based index of the last occurrence of the specified in the current . + /// The source span. + /// The value to seek within the source span. + /// One of the enumeration values that determines how the and are compared. + /// + public static int LastIndexOf(this ReadOnlySpan span, ReadOnlySpan value, StringComparison comparisonType) + { + string.CheckStringComparison(comparisonType); + + if (value.Length == 0) + { + return 0; + } + + if (span.Length == 0) + { + return -1; + } + + if (GlobalizationMode.Invariant) + { + return CompareInfo.InvariantIndexOf(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType) != CompareOptions.None, fromBeginning: false); + } + + switch (comparisonType) + { + case StringComparison.CurrentCulture: + case StringComparison.CurrentCultureIgnoreCase: + return CultureInfo.CurrentCulture.CompareInfo.LastIndexOf(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType)); + + case StringComparison.InvariantCulture: + case StringComparison.InvariantCultureIgnoreCase: + return CompareInfo.Invariant.LastIndexOf(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType)); + + default: + Debug.Assert(comparisonType == StringComparison.Ordinal || comparisonType == StringComparison.OrdinalIgnoreCase); + return CompareInfo.Invariant.LastIndexOfOrdinal(span, value, string.GetCaseCompareOfComparisonCulture(comparisonType) != CompareOptions.None); + } } /// -- 2.7.4