| | | 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 | | |
| | | 4 | | using System.Diagnostics; |
| | | 5 | | using System.Globalization; |
| | | 6 | | using System.Runtime.CompilerServices; |
| | | 7 | | using System.Runtime.InteropServices; |
| | | 8 | | using System.Runtime.Intrinsics; |
| | | 9 | | |
| | | 10 | | namespace System.Buffers |
| | | 11 | | { |
| | | 12 | | /// <summary> |
| | | 13 | | /// An implementation of the Aho-Corasick algorithm we use as a fallback when we can't use Teddy |
| | | 14 | | /// (either due to missing hardware intrinsics, or due to characteristics of the values used). |
| | | 15 | | /// https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm |
| | | 16 | | /// Works in O(n). |
| | | 17 | | /// </summary> |
| | | 18 | | internal readonly struct AhoCorasick |
| | | 19 | | { |
| | | 20 | | private readonly AhoCorasickNode[] _nodes; |
| | | 21 | | private readonly IndexOfAnyAsciiSearcher.AsciiState _startingAsciiChars; |
| | | 22 | | |
| | | 23 | | public AhoCorasick(AhoCorasickNode[] nodes, IndexOfAnyAsciiSearcher.AsciiState startingAsciiChars) |
| | | 24 | | { |
| | 0 | 25 | | _nodes = nodes; |
| | 0 | 26 | | _startingAsciiChars = startingAsciiChars; |
| | 0 | 27 | | } |
| | | 28 | | |
| | | 29 | | public readonly bool ShouldUseAsciiFastScan |
| | | 30 | | { |
| | | 31 | | get |
| | | 32 | | { |
| | 0 | 33 | | if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && _startingAsciiChars.Bitmap != default) |
| | | 34 | | { |
| | | 35 | | // If there are a lot of starting characters such that we often find one early, |
| | | 36 | | // the ASCII fast scan may end up performing worse than checking one character at a time. |
| | | 37 | | // Avoid using this optimization if the combined frequency of starting chars is too high. |
| | | 38 | | // |
| | | 39 | | // For reference, the combined frequency of characters based on CharacterFrequencyHelper.AsciiFreque |
| | | 40 | | // - All digits is ~ 5 % |
| | | 41 | | // - All lowercase letters is ~ 57.2 % |
| | | 42 | | // - All uppercase letters is ~ 7.4 % |
| | | 43 | | // |
| | | 44 | | // This limit is based on experimentation with different texts and sets of values. |
| | | 45 | | // Above ~50 %, the cost of calling into the vectorized helper is higher than checking char by char |
| | | 46 | | const float MaxCombinedFrequency = 50f; |
| | | 47 | | |
| | 0 | 48 | | float frequency = 0; |
| | | 49 | | |
| | 0 | 50 | | for (int i = 0; i < 128; i++) |
| | | 51 | | { |
| | 0 | 52 | | if (_startingAsciiChars.Lookup.Contains256((char)i)) |
| | | 53 | | { |
| | 0 | 54 | | frequency += CharacterFrequencyHelper.AsciiFrequency[i]; |
| | | 55 | | } |
| | | 56 | | } |
| | | 57 | | |
| | 0 | 58 | | return frequency <= MaxCombinedFrequency; |
| | | 59 | | } |
| | | 60 | | |
| | 0 | 61 | | return false; |
| | | 62 | | } |
| | | 63 | | } |
| | | 64 | | |
| | | 65 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 66 | | public readonly int IndexOfAny<TCaseSensitivity, TFastScanVariant>(ReadOnlySpan<char> span) |
| | | 67 | | where TCaseSensitivity : struct, StringSearchValuesHelper.ICaseSensitivity |
| | | 68 | | where TFastScanVariant : struct, IFastScan |
| | | 69 | | { |
| | 0 | 70 | | return typeof(TCaseSensitivity) == typeof(StringSearchValuesHelper.CaseInsensitiveUnicode) |
| | 0 | 71 | | ? IndexOfAnyCaseInsensitiveUnicode<TFastScanVariant>(span) |
| | 0 | 72 | | : IndexOfAnyCore<TCaseSensitivity, TFastScanVariant>(span); |
| | | 73 | | } |
| | | 74 | | |
| | | 75 | | private readonly int IndexOfAnyCore<TCaseSensitivity, TFastScanVariant>(ReadOnlySpan<char> span) |
| | | 76 | | where TCaseSensitivity : struct, StringSearchValuesHelper.ICaseSensitivity |
| | | 77 | | where TFastScanVariant : struct, IFastScan |
| | | 78 | | { |
| | 0 | 79 | | Debug.Assert(typeof(TCaseSensitivity) != typeof(StringSearchValuesHelper.CaseInsensitiveUnicode)); |
| | | 80 | | |
| | 0 | 81 | | ref AhoCorasickNode nodes = ref MemoryMarshal.GetArrayDataReference(_nodes); |
| | 0 | 82 | | int nodeIndex = 0; |
| | 0 | 83 | | int result = -1; |
| | 0 | 84 | | int i = 0; |
| | | 85 | | |
| | | 86 | | FastScan: |
| | 0 | 87 | | Debug.Assert(nodeIndex == 0); |
| | | 88 | | // We are currently in the root node and trying to find the next position of any starting character. |
| | | 89 | | // If all the values start with an ASCII character, use a vectorized helper to quickly skip over characters |
| | 0 | 90 | | if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && typeof(TFastScanVariant) == typeof(IndexOfAnyAsciiFa |
| | | 91 | | { |
| | 0 | 92 | | int remainingLength = span.Length - i; |
| | | 93 | | |
| | 0 | 94 | | if (remainingLength >= Vector128<ushort>.Count) |
| | | 95 | | { |
| | | 96 | | // If '\0' is one of the starting chars and we're running on Ssse3 hardware, this may return false-p |
| | | 97 | | // False-positives here are okay, we'll just rule them out below. While we could flow the Ssse3AndWa |
| | | 98 | | // generic through, we expect such values to be rare enough that introducing more code is not worth |
| | 0 | 99 | | int offset = IndexOfAnyAsciiSearcher.IndexOfAny<IndexOfAnyAsciiSearcher.DontNegate, IndexOfAnyAsciiS |
| | 0 | 100 | | ref Unsafe.As<char, short>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), i)), |
| | 0 | 101 | | remainingLength, |
| | 0 | 102 | | ref Unsafe.AsRef(in _startingAsciiChars)); |
| | | 103 | | |
| | 0 | 104 | | if (offset < 0) |
| | | 105 | | { |
| | | 106 | | goto Return; |
| | | 107 | | } |
| | | 108 | | |
| | 0 | 109 | | i += offset; |
| | 0 | 110 | | goto LoopWithoutRangeCheck; |
| | | 111 | | } |
| | | 112 | | } |
| | | 113 | | |
| | | 114 | | Loop: |
| | 0 | 115 | | if ((uint)i >= (uint)span.Length) |
| | | 116 | | { |
| | | 117 | | goto Return; |
| | | 118 | | } |
| | | 119 | | |
| | | 120 | | LoopWithoutRangeCheck: |
| | | 121 | | // Read the next input character and either find the next potential match prefix or transition back to the r |
| | 0 | 122 | | Debug.Assert((uint)i < (uint)span.Length); |
| | 0 | 123 | | char c = TCaseSensitivity.TransformInput(Unsafe.Add(ref MemoryMarshal.GetReference(span), i)); |
| | | 124 | | |
| | | 125 | | while (true) |
| | | 126 | | { |
| | 0 | 127 | | Debug.Assert((uint)nodeIndex < (uint)_nodes.Length); |
| | 0 | 128 | | ref AhoCorasickNode node = ref Unsafe.Add(ref nodes, (uint)nodeIndex); |
| | | 129 | | |
| | 0 | 130 | | if (node.TryGetChild(c, out int childIndex)) |
| | | 131 | | { |
| | | 132 | | // We were able to extend the current match. If this node contains a potential match, remember that. |
| | 0 | 133 | | nodeIndex = childIndex; |
| | | 134 | | |
| | 0 | 135 | | Debug.Assert((uint)nodeIndex < (uint)_nodes.Length); |
| | 0 | 136 | | int matchLength = Unsafe.Add(ref nodes, (uint)nodeIndex).MatchLength; |
| | 0 | 137 | | if (matchLength != 0) |
| | | 138 | | { |
| | | 139 | | // Any result we find from here on out may only be lower (longer match with a start closer to th |
| | 0 | 140 | | Debug.Assert(result == -1 || result >= i + 1 - matchLength); |
| | 0 | 141 | | result = i + 1 - matchLength; |
| | | 142 | | } |
| | | 143 | | |
| | 0 | 144 | | i++; |
| | 0 | 145 | | goto Loop; |
| | | 146 | | } |
| | | 147 | | |
| | 0 | 148 | | if (nodeIndex == 0) |
| | | 149 | | { |
| | | 150 | | // We are back at the root node and none of the values start with the current character. |
| | 0 | 151 | | if (result >= 0) |
| | | 152 | | { |
| | | 153 | | // If we've already found a match, we can't find an earlier one anymore. This is the result |
| | | 154 | | goto Return; |
| | | 155 | | } |
| | | 156 | | |
| | | 157 | | // Go back to searching for the next possible starting character. |
| | 0 | 158 | | i++; |
| | 0 | 159 | | goto FastScan; |
| | | 160 | | } |
| | | 161 | | |
| | | 162 | | // Follow the next suffix link. |
| | 0 | 163 | | nodeIndex = node.SuffixLink; |
| | | 164 | | |
| | 0 | 165 | | if (nodeIndex < 0) |
| | | 166 | | { |
| | | 167 | | // A node with a suffix link of -1 indicates a match, see AhoCorasickBuilder.AddSuffixLinks. |
| | 0 | 168 | | Debug.Assert(nodeIndex == -1); |
| | 0 | 169 | | Debug.Assert(result >= 0); |
| | | 170 | | goto Return; |
| | | 171 | | } |
| | | 172 | | |
| | | 173 | | // Try to match the current character again at the suffix link node. |
| | | 174 | | } |
| | | 175 | | |
| | | 176 | | Return: |
| | 0 | 177 | | return result; |
| | | 178 | | } |
| | | 179 | | |
| | | 180 | | // Mostly a copy of IndexOfAnyCore, but we may read two characters at a time in the case of surrogate pairs. |
| | | 181 | | private readonly int IndexOfAnyCaseInsensitiveUnicode<TFastScanVariant>(ReadOnlySpan<char> span) |
| | | 182 | | where TFastScanVariant : struct, IFastScan |
| | | 183 | | { |
| | | 184 | | const char LowSurrogateNotSet = '\0'; |
| | | 185 | | |
| | 0 | 186 | | ref AhoCorasickNode nodes = ref MemoryMarshal.GetArrayDataReference(_nodes); |
| | 0 | 187 | | int nodeIndex = 0; |
| | 0 | 188 | | int result = -1; |
| | 0 | 189 | | int i = 0; |
| | 0 | 190 | | char lowSurrogateUpper = LowSurrogateNotSet; |
| | | 191 | | |
| | | 192 | | FastScan: |
| | | 193 | | // We are currently in the root node and trying to find the next position of any starting character. |
| | | 194 | | // If all the values start with an ASCII character, use a vectorized helper to quickly skip over characters |
| | 0 | 195 | | if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && typeof(TFastScanVariant) == typeof(IndexOfAnyAsciiFa |
| | | 196 | | { |
| | 0 | 197 | | if (lowSurrogateUpper != LowSurrogateNotSet) |
| | | 198 | | { |
| | | 199 | | // We read a surrogate pair in the previous loop iteration and processed the high surrogate. |
| | | 200 | | // Continue with the stored low surrogate. |
| | | 201 | | goto LoopWithoutRangeCheck; |
| | | 202 | | } |
| | | 203 | | |
| | 0 | 204 | | int remainingLength = span.Length - i; |
| | | 205 | | |
| | 0 | 206 | | if (remainingLength >= Vector128<ushort>.Count) |
| | | 207 | | { |
| | 0 | 208 | | int offset = IndexOfAnyAsciiSearcher.IndexOfAny<IndexOfAnyAsciiSearcher.DontNegate, IndexOfAnyAsciiS |
| | 0 | 209 | | ref Unsafe.As<char, short>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), i)), |
| | 0 | 210 | | remainingLength, |
| | 0 | 211 | | ref Unsafe.AsRef(in _startingAsciiChars)); |
| | | 212 | | |
| | 0 | 213 | | if (offset < 0) |
| | | 214 | | { |
| | | 215 | | goto Return; |
| | | 216 | | } |
| | | 217 | | |
| | 0 | 218 | | i += offset; |
| | 0 | 219 | | goto LoopWithoutRangeCheck; |
| | | 220 | | } |
| | | 221 | | } |
| | | 222 | | |
| | | 223 | | Loop: |
| | 0 | 224 | | if ((uint)i >= (uint)span.Length) |
| | | 225 | | { |
| | | 226 | | goto Return; |
| | | 227 | | } |
| | | 228 | | |
| | | 229 | | LoopWithoutRangeCheck: |
| | | 230 | | // Read the next input character and either find the next potential match prefix or transition back to the r |
| | 0 | 231 | | Debug.Assert((uint)i < (uint)span.Length); |
| | | 232 | | char c; |
| | 0 | 233 | | if (lowSurrogateUpper != LowSurrogateNotSet) |
| | | 234 | | { |
| | | 235 | | // We have just processed the high surrogate. Continue with the low surrogate we read in the previous it |
| | 0 | 236 | | c = lowSurrogateUpper; |
| | 0 | 237 | | lowSurrogateUpper = LowSurrogateNotSet; |
| | | 238 | | } |
| | | 239 | | else |
| | | 240 | | { |
| | | 241 | | // Read the next character, check if it's a high surrogate, and transform it to its Ordinal uppercase re |
| | 0 | 242 | | c = Unsafe.Add(ref MemoryMarshal.GetReference(span), i); |
| | | 243 | | char lowSurrogate; |
| | | 244 | | |
| | 0 | 245 | | if (char.IsHighSurrogate(c) && |
| | 0 | 246 | | (uint)(i + 1) < (uint)span.Length && |
| | 0 | 247 | | char.IsLowSurrogate(lowSurrogate = Unsafe.Add(ref MemoryMarshal.GetReference(span), i + 1))) |
| | | 248 | | { |
| | 0 | 249 | | if (GlobalizationMode.UseNls) |
| | | 250 | | { |
| | 0 | 251 | | SurrogateToUpperNLS(c, lowSurrogate, out c, out lowSurrogateUpper); |
| | | 252 | | } |
| | | 253 | | else |
| | | 254 | | { |
| | 0 | 255 | | SurrogateCasing.ToUpper(c, lowSurrogate, out c, out lowSurrogateUpper); |
| | | 256 | | } |
| | | 257 | | |
| | 0 | 258 | | Debug.Assert(lowSurrogateUpper != LowSurrogateNotSet); |
| | | 259 | | } |
| | | 260 | | else |
| | | 261 | | { |
| | 0 | 262 | | c = TextInfo.ToUpperOrdinal(c); |
| | | 263 | | } |
| | | 264 | | |
| | | 265 | | #if DEBUG |
| | | 266 | | // The above logic must match Ordinal.ToUpperOrdinal exactly. |
| | 0 | 267 | | Span<char> destination = new char[2]; // Avoid stackalloc in a loop |
| | 0 | 268 | | Ordinal.ToUpperOrdinal(span.Slice(i, i + 1 == span.Length ? 1 : 2), destination); |
| | 0 | 269 | | Debug.Assert(c == destination[0]); |
| | 0 | 270 | | Debug.Assert(lowSurrogateUpper == LowSurrogateNotSet || lowSurrogateUpper == destination[1]); |
| | | 271 | | #endif |
| | | 272 | | } |
| | | 273 | | |
| | | 274 | | while (true) |
| | | 275 | | { |
| | 0 | 276 | | Debug.Assert((uint)nodeIndex < (uint)_nodes.Length); |
| | 0 | 277 | | ref AhoCorasickNode node = ref Unsafe.Add(ref nodes, (uint)nodeIndex); |
| | | 278 | | |
| | 0 | 279 | | if (node.TryGetChild(c, out int childIndex)) |
| | | 280 | | { |
| | | 281 | | // We were able to extend the current match. If this node contains a potential match, remember that. |
| | 0 | 282 | | nodeIndex = childIndex; |
| | | 283 | | |
| | 0 | 284 | | Debug.Assert((uint)nodeIndex < (uint)_nodes.Length); |
| | 0 | 285 | | int matchLength = Unsafe.Add(ref nodes, (uint)nodeIndex).MatchLength; |
| | 0 | 286 | | if (matchLength != 0) |
| | | 287 | | { |
| | | 288 | | // Any result we find from here on out may only be lower (longer match with a start closer to th |
| | 0 | 289 | | Debug.Assert(result == -1 || result >= i + 1 - matchLength); |
| | 0 | 290 | | result = i + 1 - matchLength; |
| | | 291 | | } |
| | | 292 | | |
| | 0 | 293 | | i++; |
| | 0 | 294 | | goto Loop; |
| | | 295 | | } |
| | | 296 | | |
| | 0 | 297 | | if (nodeIndex == 0) |
| | | 298 | | { |
| | | 299 | | // We are back at the root node and none of the values start with the current character. |
| | 0 | 300 | | if (result >= 0) |
| | | 301 | | { |
| | | 302 | | // If we've already found a match, we can't find an earlier one anymore. This is the result |
| | | 303 | | goto Return; |
| | | 304 | | } |
| | | 305 | | |
| | | 306 | | // Go back to searching for the next possible starting character. |
| | 0 | 307 | | i++; |
| | 0 | 308 | | goto FastScan; |
| | | 309 | | } |
| | | 310 | | |
| | | 311 | | // Follow the next suffix link. |
| | 0 | 312 | | nodeIndex = node.SuffixLink; |
| | | 313 | | |
| | 0 | 314 | | if (nodeIndex < 0) |
| | | 315 | | { |
| | | 316 | | // A node with a suffix link of -1 indicates a match, see AhoCorasickBuilder.AddSuffixLinks. |
| | 0 | 317 | | Debug.Assert(nodeIndex == -1); |
| | 0 | 318 | | Debug.Assert(result >= 0); |
| | | 319 | | goto Return; |
| | | 320 | | } |
| | | 321 | | |
| | | 322 | | // Try to match the current character again at the suffix link node. |
| | | 323 | | } |
| | | 324 | | |
| | | 325 | | Return: |
| | 0 | 326 | | return result; |
| | | 327 | | } |
| | | 328 | | |
| | | 329 | | private static void SurrogateToUpperNLS(char h, char l, out char hr, out char lr) |
| | | 330 | | { |
| | 0 | 331 | | Debug.Assert(char.IsHighSurrogate(h)); |
| | 0 | 332 | | Debug.Assert(char.IsLowSurrogate(l)); |
| | | 333 | | |
| | 0 | 334 | | ReadOnlySpan<char> chars = [h, l]; |
| | 0 | 335 | | Span<char> destination = ['\0', '\0']; |
| | | 336 | | |
| | 0 | 337 | | int written = Ordinal.ToUpperOrdinal(chars, destination); |
| | 0 | 338 | | Debug.Assert(written == 2); |
| | | 339 | | |
| | 0 | 340 | | hr = destination[0]; |
| | 0 | 341 | | lr = destination[1]; |
| | | 342 | | |
| | 0 | 343 | | Debug.Assert(char.IsHighSurrogate(hr)); |
| | 0 | 344 | | Debug.Assert(char.IsLowSurrogate(lr)); |
| | 0 | 345 | | } |
| | | 346 | | |
| | | 347 | | public interface IFastScan { } |
| | | 348 | | |
| | | 349 | | public readonly struct IndexOfAnyAsciiFastScan : IFastScan { } |
| | | 350 | | |
| | | 351 | | public readonly struct NoFastScan : IFastScan { } |
| | | 352 | | } |
| | | 353 | | } |
| | | 354 | | |