src/mscorlib/shared/System/String.Searching.cs

   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.Globalization;
   6 using System.Runtime.InteropServices;
   7
   8 namespace System
   9 {
  10     public partial class String
  11     {
  12         public bool Contains(string value)
  13         {
  14             return (IndexOf(value, StringComparison.Ordinal) >= 0);
  15         }
  16
  17         public bool Contains(string value, StringComparison comparisonType)
  18         {
  19             return (IndexOf(value, comparisonType) >= 0);
  20         }
  21
  22         public bool Contains(char value)
  23         {
  24             return IndexOf(value) != -1;
  25         }
  26
  27         public bool Contains(char value, StringComparison comparisonType)
  28         {
  29             return IndexOf(value, comparisonType) != -1;
  30         }
  31
  32         // Returns the index of the first occurrence of a specified character in the current instance.
  33         // The search starts at startIndex and runs thorough the next count characters.
  34         //
  35         public int IndexOf(char value)
  36         {
  37             return IndexOf(value, 0, this.Length);
  38         }
  39
  40         public int IndexOf(char value, int startIndex)
  41         {
  42             return IndexOf(value, startIndex, this.Length - startIndex);
  43         }
  44
  45         public int IndexOf(char value, StringComparison comparisonType)
  46         {
  47             switch (comparisonType)
  48             {
  49                 case StringComparison.CurrentCulture:
  50                     return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, CompareOptions.None);
  51
  52                 case StringComparison.CurrentCultureIgnoreCase:
  53                     return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, CompareOptions.IgnoreCase);
  54
  55                 case StringComparison.InvariantCulture:
  56                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, CompareOptions.None);
  57
  58                 case StringComparison.InvariantCultureIgnoreCase:
  59                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, CompareOptions.IgnoreCase);
  60
  61                 case StringComparison.Ordinal:
  62                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, CompareOptions.Ordinal);
  63
  64                 case StringComparison.OrdinalIgnoreCase:
  65                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, CompareOptions.OrdinalIgnoreCase);
  66
  67                 default:
  68                     throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType));
  69             }
  70         }
  71
  72         public unsafe int IndexOf(char value, int startIndex, int count)
  73         {
  74             if (startIndex < 0 || startIndex > Length)
  75                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
  76
  77             if (count < 0 || count > Length - startIndex)
  78                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
  79
  80             fixed (char* pChars = &_firstChar)
  81             {
  82                 char* pCh = pChars + startIndex;
  83
  84                 while (count >= 4)
  85                 {
  86                     if (*pCh == value) goto ReturnIndex;
  87                     if (*(pCh + 1) == value) goto ReturnIndex1;
  88                     if (*(pCh + 2) == value) goto ReturnIndex2;
  89                     if (*(pCh + 3) == value) goto ReturnIndex3;
  90
  91                     count -= 4;
  92                     pCh += 4;
  93                 }
  94
  95                 while (count > 0)
  96                 {
  97                     if (*pCh == value)
  98                         goto ReturnIndex;
  99
 100                     count--;
 101                     pCh++;
 102                 }
 103
 104                 return -1;
 105
 106             ReturnIndex3: pCh++;
 107             ReturnIndex2: pCh++;
 108             ReturnIndex1: pCh++;
 109             ReturnIndex:
 110                 return (int)(pCh - pChars);
 111             }
 112         }
 113
 114         // Returns the index of the first occurrence of any specified character in the current instance.
 115         // The search starts at startIndex and runs to startIndex + count - 1.
 116         //
 117         public int IndexOfAny(char[] anyOf)
 118         {
 119             return IndexOfAny(anyOf, 0, this.Length);
 120         }
 121
 122         public int IndexOfAny(char[] anyOf, int startIndex)
 123         {
 124             return IndexOfAny(anyOf, startIndex, this.Length - startIndex);
 125         }
 126
 127         public int IndexOfAny(char[] anyOf, int startIndex, int count)
 128         {
 129             if (anyOf == null)
 130                 throw new ArgumentNullException(nameof(anyOf));
 131
 132             if ((uint)startIndex > (uint)Length)
 133                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 134
 135             if ((uint)count > (uint)(Length - startIndex))
 136                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 137
 138             if (anyOf.Length == 2)
 139             {
 140                 // Very common optimization for directory separators (/, \), quotes (", '), brackets, etc
 141                 return IndexOfAny(anyOf[0], anyOf[1], startIndex, count);
 142             }
 143             else if (anyOf.Length == 3)
 144             {
 145                 return IndexOfAny(anyOf[0], anyOf[1], anyOf[2], startIndex, count);
 146             }
 147             else if (anyOf.Length > 3)
 148             {
 149                 return IndexOfCharArray(anyOf, startIndex, count);
 150             }
 151             else if (anyOf.Length == 1)
 152             {
 153                 return IndexOf(anyOf[0], startIndex, count);
 154             }
 155             else // anyOf.Length == 0
 156             {
 157                 return -1;
 158             }
 159         }
 160
 161         private unsafe int IndexOfAny(char value1, char value2, int startIndex, int count)
 162         {
 163             fixed (char* pChars = &_firstChar)
 164             {
 165                 char* pCh = pChars + startIndex;
 166
 167                 while (count > 0)
 168                 {
 169                     char c = *pCh;
 170
 171                     if (c == value1 || c == value2)
 172                         return (int)(pCh - pChars);
 173
 174                     // Possibly reads outside of count and can include null terminator
 175                     // Handled in the return logic
 176                     c = *(pCh + 1);
 177
 178                     if (c == value1 || c == value2)
 179                         return (count == 1 ? -1 : (int)(pCh - pChars) + 1);
 180
 181                     pCh += 2;
 182                     count -= 2;
 183                 }
 184
 185                 return -1;
 186             }
 187         }
 188
 189         private unsafe int IndexOfAny(char value1, char value2, char value3, int startIndex, int count)
 190         {
 191             fixed (char* pChars = &_firstChar)
 192             {
 193                 char* pCh = pChars + startIndex;
 194
 195                 while (count > 0)
 196                 {
 197                     char c = *pCh;
 198
 199                     if (c == value1 || c == value2 || c == value3)
 200                         return (int)(pCh - pChars);
 201
 202                     pCh++;
 203                     count--;
 204                 }
 205
 206                 return -1;
 207             }
 208         }
 209
 210         private unsafe int IndexOfCharArray(char[] anyOf, int startIndex, int count)
 211         {
 212             // use probabilistic map, see InitializeProbabilisticMap
 213             ProbabilisticMap map = default(ProbabilisticMap);
 214             uint* charMap = (uint*)&map;
 215
 216             InitializeProbabilisticMap(charMap, anyOf);
 217
 218             fixed (char* pChars = &_firstChar)
 219             {
 220                 char* pCh = pChars + startIndex;
 221
 222                 while (count > 0)
 223                 {
 224                     int thisChar = *pCh;
 225
 226                     if (IsCharBitSet(charMap, (byte)thisChar) &&
 227                         IsCharBitSet(charMap, (byte)(thisChar >> 8)) &&
 228                         ArrayContains((char)thisChar, anyOf))
 229                     {
 230                         return (int)(pCh - pChars);
 231                     }
 232
 233                     count--;
 234                     pCh++;
 235                 }
 236
 237                 return -1;
 238             }
 239         }
 240
 241         private const int PROBABILISTICMAP_BLOCK_INDEX_MASK = 0x7;
 242         private const int PROBABILISTICMAP_BLOCK_INDEX_SHIFT = 0x3;
 243         private const int PROBABILISTICMAP_SIZE = 0x8;
 244
 245         // A probabilistic map is an optimization that is used in IndexOfAny/
 246         // LastIndexOfAny methods. The idea is to create a bit map of the characters we
 247         // are searching for and use this map as a "cheap" check to decide if the
 248         // current character in the string exists in the array of input characters.
 249         // There are 256 bits in the map, with each character mapped to 2 bits. Every
 250         // character is divided into 2 bytes, and then every byte is mapped to 1 bit.
 251         // The character map is an array of 8 integers acting as map blocks. The 3 lsb
 252         // in each byte in the character is used to index into this map to get the
 253         // right block, the value of the remaining 5 msb are used as the bit position
 254         // inside this block.
 255         private static unsafe void InitializeProbabilisticMap(uint* charMap, ReadOnlySpan<char> anyOf)
 256         {
 257             bool hasAscii = false;
 258             uint* charMapLocal = charMap; // https://github.com/dotnet/coreclr/issues/14264
 259
 260             for (int i = 0; i < anyOf.Length; ++i)
 261             {
 262                 int c = anyOf[i];
 263
 264                 // Map low bit
 265                 SetCharBit(charMapLocal, (byte)c);
 266
 267                 // Map high bit
 268                 c >>= 8;
 269
 270                 if (c == 0)
 271                 {
 272                     hasAscii = true;
 273                 }
 274                 else
 275                 {
 276                     SetCharBit(charMapLocal, (byte)c);
 277                 }
 278             }
 279
 280             if (hasAscii)
 281             {
 282                 // Common to search for ASCII symbols. Just set the high value once.
 283                 charMapLocal[0] |= 1u;
 284             }
 285         }
 286
 287         private static bool ArrayContains(char searchChar, char[] anyOf)
 288         {
 289             for (int i = 0; i < anyOf.Length; i++)
 290             {
 291                 if (anyOf[i] == searchChar)
 292                     return true;
 293             }
 294
 295             return false;
 296         }
 297
 298         private unsafe static bool IsCharBitSet(uint* charMap, byte value)
 299         {
 300             return (charMap[value & PROBABILISTICMAP_BLOCK_INDEX_MASK] & (1u << (value >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT))) != 0;
 301         }
 302
 303         private unsafe static void SetCharBit(uint* charMap, byte value)
 304         {
 305             charMap[value & PROBABILISTICMAP_BLOCK_INDEX_MASK] |= 1u << (value >> PROBABILISTICMAP_BLOCK_INDEX_SHIFT);
 306         }
 307
 308         public int IndexOf(String value)
 309         {
 310             return IndexOf(value, StringComparison.CurrentCulture);
 311         }
 312
 313         public int IndexOf(String value, int startIndex)
 314         {
 315             return IndexOf(value, startIndex, StringComparison.CurrentCulture);
 316         }
 317
 318         public int IndexOf(String value, int startIndex, int count)
 319         {
 320             if (startIndex < 0 || startIndex > this.Length)
 321             {
 322                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 323             }
 324
 325             if (count < 0 || count > this.Length - startIndex)
 326             {
 327                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 328             }
 329
 330             return IndexOf(value, startIndex, count, StringComparison.CurrentCulture);
 331         }
 332
 333         public int IndexOf(String value, StringComparison comparisonType)
 334         {
 335             return IndexOf(value, 0, this.Length, comparisonType);
 336         }
 337
 338         public int IndexOf(String value, int startIndex, StringComparison comparisonType)
 339         {
 340             return IndexOf(value, startIndex, this.Length - startIndex, comparisonType);
 341         }
 342
 343         public int IndexOf(String value, int startIndex, int count, StringComparison comparisonType)
 344         {
 345             // Validate inputs
 346             if (value == null)
 347                 throw new ArgumentNullException(nameof(value));
 348
 349             if (startIndex < 0 || startIndex > this.Length)
 350                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 351
 352             if (count < 0 || startIndex > this.Length - count)
 353                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 354
 355             switch (comparisonType)
 356             {
 357                 case StringComparison.CurrentCulture:
 358                     return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.None);
 359
 360                 case StringComparison.CurrentCultureIgnoreCase:
 361                     return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
 362
 363                 case StringComparison.InvariantCulture:
 364                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.None);
 365
 366                 case StringComparison.InvariantCultureIgnoreCase:
 367                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
 368
 369                 case StringComparison.Ordinal:
 370                     return CultureInfo.InvariantCulture.CompareInfo.IndexOf(this, value, startIndex, count, CompareOptions.Ordinal);
 371
 372                 case StringComparison.OrdinalIgnoreCase:
 373                     return TextInfo.IndexOfStringOrdinalIgnoreCase(this, value, startIndex, count);
 374
 375                 default:
 376                     throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType));
 377             }
 378         }
 379
 380         // Returns the index of the last occurrence of a specified character in the current instance.
 381         // The search starts at startIndex and runs backwards to startIndex - count + 1.
 382         // The character at position startIndex is included in the search.  startIndex is the larger
 383         // index within the string.
 384         //
 385         public int LastIndexOf(char value)
 386         {
 387             return LastIndexOf(value, this.Length - 1, this.Length);
 388         }
 389
 390         public int LastIndexOf(char value, int startIndex)
 391         {
 392             return LastIndexOf(value, startIndex, startIndex + 1);
 393         }
 394
 395         public unsafe int LastIndexOf(char value, int startIndex, int count)
 396         {
 397             if (Length == 0)
 398                 return -1;
 399
 400             if (startIndex < 0 || startIndex >= Length)
 401                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 402
 403             if (count < 0 || count - 1 > startIndex)
 404                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 405
 406             fixed (char* pChars = &_firstChar)
 407             {
 408                 char* pCh = pChars + startIndex;
 409
 410                 //We search [startIndex..EndIndex]
 411                 while (count >= 4)
 412                 {
 413                     if (*pCh == value) goto ReturnIndex;
 414                     if (*(pCh - 1) == value) goto ReturnIndex1;
 415                     if (*(pCh - 2) == value) goto ReturnIndex2;
 416                     if (*(pCh - 3) == value) goto ReturnIndex3;
 417
 418                     count -= 4;
 419                     pCh -= 4;
 420                 }
 421
 422                 while (count > 0)
 423                 {
 424                     if (*pCh == value)
 425                         goto ReturnIndex;
 426
 427                     count--;
 428                     pCh--;
 429                 }
 430
 431                 return -1;
 432
 433             ReturnIndex3: pCh--;
 434             ReturnIndex2: pCh--;
 435             ReturnIndex1: pCh--;
 436             ReturnIndex:
 437                 return (int)(pCh - pChars);
 438             }
 439         }
 440
 441         // Returns the index of the last occurrence of any specified character in the current instance.
 442         // The search starts at startIndex and runs backwards to startIndex - count + 1.
 443         // The character at position startIndex is included in the search.  startIndex is the larger
 444         // index within the string.
 445         //
 446         public int LastIndexOfAny(char[] anyOf)
 447         {
 448             return LastIndexOfAny(anyOf, this.Length - 1, this.Length);
 449         }
 450
 451         public int LastIndexOfAny(char[] anyOf, int startIndex)
 452         {
 453             return LastIndexOfAny(anyOf, startIndex, startIndex + 1);
 454         }
 455
 456         public unsafe int LastIndexOfAny(char[] anyOf, int startIndex, int count)
 457         {
 458             if (anyOf == null)
 459                 throw new ArgumentNullException(nameof(anyOf));
 460
 461             if (Length == 0)
 462                 return -1;
 463
 464             if ((uint)startIndex >= (uint)Length)
 465             {
 466                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 467             }
 468
 469             if ((count < 0) || ((count - 1) > startIndex))
 470             {
 471                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 472             }
 473
 474             if (anyOf.Length > 1)
 475             {
 476                 return LastIndexOfCharArray(anyOf, startIndex, count);
 477             }
 478             else if (anyOf.Length == 1)
 479             {
 480                 return LastIndexOf(anyOf[0], startIndex, count);
 481             }
 482             else // anyOf.Length == 0
 483             {
 484                 return -1;
 485             }
 486         }
 487
 488         private unsafe int LastIndexOfCharArray(char[] anyOf, int startIndex, int count)
 489         {
 490             // use probabilistic map, see InitializeProbabilisticMap
 491             ProbabilisticMap map = default(ProbabilisticMap);
 492             uint* charMap = (uint*)&map;
 493
 494             InitializeProbabilisticMap(charMap, anyOf);
 495
 496             fixed (char* pChars = &_firstChar)
 497             {
 498                 char* pCh = pChars + startIndex;
 499
 500                 while (count > 0)
 501                 {
 502                     int thisChar = *pCh;
 503
 504                     if (IsCharBitSet(charMap, (byte)thisChar) &&
 505                         IsCharBitSet(charMap, (byte)(thisChar >> 8)) &&
 506                         ArrayContains((char)thisChar, anyOf))
 507                     {
 508                         return (int)(pCh - pChars);
 509                     }
 510
 511                     count--;
 512                     pCh--;
 513                 }
 514
 515                 return -1;
 516             }
 517         }
 518
 519         // Returns the index of the last occurrence of any character in value in the current instance.
 520         // The search starts at startIndex and runs backwards to startIndex - count + 1.
 521         // The character at position startIndex is included in the search.  startIndex is the larger
 522         // index within the string.
 523         //
 524         public int LastIndexOf(String value)
 525         {
 526             return LastIndexOf(value, this.Length - 1, this.Length, StringComparison.CurrentCulture);
 527         }
 528
 529         public int LastIndexOf(String value, int startIndex)
 530         {
 531             return LastIndexOf(value, startIndex, startIndex + 1, StringComparison.CurrentCulture);
 532         }
 533
 534         public int LastIndexOf(String value, int startIndex, int count)
 535         {
 536             if (count < 0)
 537             {
 538                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 539             }
 540
 541             return LastIndexOf(value, startIndex, count, StringComparison.CurrentCulture);
 542         }
 543
 544         public int LastIndexOf(String value, StringComparison comparisonType)
 545         {
 546             return LastIndexOf(value, this.Length - 1, this.Length, comparisonType);
 547         }
 548
 549         public int LastIndexOf(String value, int startIndex, StringComparison comparisonType)
 550         {
 551             return LastIndexOf(value, startIndex, startIndex + 1, comparisonType);
 552         }
 553
 554         public int LastIndexOf(String value, int startIndex, int count, StringComparison comparisonType)
 555         {
 556             if (value == null)
 557                 throw new ArgumentNullException(nameof(value));
 558
 559             // Special case for 0 length input strings
 560             if (this.Length == 0 && (startIndex == -1 || startIndex == 0))
 561                 return (value.Length == 0) ? 0 : -1;
 562
 563             // Now after handling empty strings, make sure we're not out of range
 564             if (startIndex < 0 || startIndex > this.Length)
 565                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 566
 567             // Make sure that we allow startIndex == this.Length
 568             if (startIndex == this.Length)
 569             {
 570                 startIndex--;
 571                 if (count > 0)
 572                     count--;
 573             }
 574
 575             // 2nd half of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
 576             if (count < 0 || startIndex - count + 1 < 0)
 577                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 578
 579             // If we are looking for nothing, just return startIndex
 580             if (value.Length == 0)
 581                 return startIndex;
 582
 583             switch (comparisonType)
 584             {
 585                 case StringComparison.CurrentCulture:
 586                     return CultureInfo.CurrentCulture.CompareInfo.LastIndexOf(this, value, startIndex, count, CompareOptions.None);
 587
 588                 case StringComparison.CurrentCultureIgnoreCase:
 589                     return CultureInfo.CurrentCulture.CompareInfo.LastIndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
 590
 591                 case StringComparison.InvariantCulture:
 592                     return CultureInfo.InvariantCulture.CompareInfo.LastIndexOf(this, value, startIndex, count, CompareOptions.None);
 593
 594                 case StringComparison.InvariantCultureIgnoreCase:
 595                     return CultureInfo.InvariantCulture.CompareInfo.LastIndexOf(this, value, startIndex, count, CompareOptions.IgnoreCase);
 596
 597                 case StringComparison.Ordinal:
 598                     return CultureInfo.InvariantCulture.CompareInfo.LastIndexOf(this, value, startIndex, count, CompareOptions.Ordinal);
 599
 600                 case StringComparison.OrdinalIgnoreCase:
 601                     return TextInfo.LastIndexOfStringOrdinalIgnoreCase(this, value, startIndex, count);
 602
 603                 default:
 604                     throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType));
 605             }
 606         }
 607
 608         [StructLayout(LayoutKind.Explicit, Size = PROBABILISTICMAP_SIZE * sizeof(uint))]
 609         private struct ProbabilisticMap { }
 610     }
 611 }