src/mscorlib/shared/System/String.Manipulation.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.Buffers;
   6 using System.Collections.Generic;
   7 using System.Diagnostics;
   8 using System.Globalization;
   9 using System.Runtime.CompilerServices;
  10 using System.Runtime.InteropServices;
  11 using System.Text;
  12 using Internal.Runtime.CompilerServices;
  13
  14 namespace System
  15 {
  16     public partial class String
  17     {
  18         private const int StackallocIntBufferSizeLimit = 128;
  19
  20         private static unsafe void FillStringChecked(string dest, int destPos, string src)
  21         {
  22             Debug.Assert(dest != null);
  23             Debug.Assert(src != null);
  24             if (src.Length > dest.Length - destPos)
  25             {
  26                 throw new IndexOutOfRangeException();
  27             }
  28
  29             fixed (char* pDest = &dest._firstChar)
  30             fixed (char* pSrc = &src._firstChar)
  31             {
  32                 wstrcpy(pDest + destPos, pSrc, src.Length);
  33             }
  34         }
  35
  36         public static string Concat(object arg0)
  37         {
  38             if (arg0 == null)
  39             {
  40                 return string.Empty;
  41             }
  42             return arg0.ToString();
  43         }
  44
  45         public static string Concat(object arg0, object arg1)
  46         {
  47             if (arg0 == null)
  48             {
  49                 arg0 = string.Empty;
  50             }
  51
  52             if (arg1 == null)
  53             {
  54                 arg1 = string.Empty;
  55             }
  56             return Concat(arg0.ToString(), arg1.ToString());
  57         }
  58
  59         public static string Concat(object arg0, object arg1, object arg2)
  60         {
  61             if (arg0 == null)
  62             {
  63                 arg0 = string.Empty;
  64             }
  65
  66             if (arg1 == null)
  67             {
  68                 arg1 = string.Empty;
  69             }
  70
  71             if (arg2 == null)
  72             {
  73                 arg2 = string.Empty;
  74             }
  75
  76             return Concat(arg0.ToString(), arg1.ToString(), arg2.ToString());
  77         }
  78
  79         public static string Concat(params object[] args)
  80         {
  81             if (args == null)
  82             {
  83                 throw new ArgumentNullException(nameof(args));
  84             }
  85
  86             if (args.Length <= 1)
  87             {
  88                 return args.Length == 0 ?
  89                     string.Empty :
  90                     args[0]?.ToString() ?? string.Empty;
  91             }
  92
  93             // We need to get an intermediary string array
  94             // to fill with each of the args' ToString(),
  95             // and then just concat that in one operation.
  96
  97             // This way we avoid any intermediary string representations,
  98             // or buffer resizing if we use StringBuilder (although the
  99             // latter case is partially alleviated due to StringBuilder's
 100             // linked-list style implementation)
 101
 102             var strings = new string[args.Length];
 103
 104             int totalLength = 0;
 105
 106             for (int i = 0; i < args.Length; i++)
 107             {
 108                 object value = args[i];
 109
 110                 string toString = value?.ToString() ?? string.Empty; // We need to handle both the cases when value or value.ToString() is null
 111                 strings[i] = toString;
 112
 113                 totalLength += toString.Length;
 114
 115                 if (totalLength < 0) // Check for a positive overflow
 116                 {
 117                     throw new OutOfMemoryException();
 118                 }
 119             }
 120
 121             // If all of the ToStrings are null/empty, just return string.Empty
 122             if (totalLength == 0)
 123             {
 124                 return string.Empty;
 125             }
 126
 127             string result = FastAllocateString(totalLength);
 128             int position = 0; // How many characters we've copied so far
 129
 130             for (int i = 0; i < strings.Length; i++)
 131             {
 132                 string s = strings[i];
 133
 134                 Debug.Assert(s != null);
 135                 Debug.Assert(position <= totalLength - s.Length, "We didn't allocate enough space for the result string!");
 136
 137                 FillStringChecked(result, position, s);
 138                 position += s.Length;
 139             }
 140
 141             return result;
 142         }
 143
 144         public static string Concat<T>(IEnumerable<T> values)
 145         {
 146             if (values == null)
 147                 throw new ArgumentNullException(nameof(values));
 148
 149             if (typeof(T) == typeof(char))
 150             {
 151                 // Special-case T==char, as we can handle that case much more efficiently,
 152                 // and string.Concat(IEnumerable<char>) can be used as an efficient
 153                 // enumerable-based equivalent of new string(char[]).
 154                 using (IEnumerator<char> en = Unsafe.As<IEnumerable<char>>(values).GetEnumerator())
 155                 {
 156                     if (!en.MoveNext())
 157                     {
 158                         // There weren't any chars.  Return the empty string.
 159                         return Empty;
 160                     }
 161
 162                     char c = en.Current; // save the first char
 163
 164                     if (!en.MoveNext())
 165                     {
 166                         // There was only one char.  Return a string from it directly.
 167                         return CreateFromChar(c);
 168                     }
 169
 170                     // Create the StringBuilder, add the chars we've already enumerated,
 171                     // add the rest, and then get the resulting string.
 172                     StringBuilder result = StringBuilderCache.Acquire();
 173                     result.Append(c); // first value
 174                     do
 175                     {
 176                         c = en.Current;
 177                         result.Append(c);
 178                     }
 179                     while (en.MoveNext());
 180                     return StringBuilderCache.GetStringAndRelease(result);
 181                 }
 182             }
 183             else
 184             {
 185                 using (IEnumerator<T> en = values.GetEnumerator())
 186                 {
 187                     if (!en.MoveNext())
 188                         return string.Empty;
 189
 190                     // We called MoveNext once, so this will be the first item
 191                     T currentValue = en.Current;
 192
 193                     // Call ToString before calling MoveNext again, since
 194                     // we want to stay consistent with the below loop
 195                     // Everything should be called in the order
 196                     // MoveNext-Current-ToString, unless further optimizations
 197                     // can be made, to avoid breaking changes
 198                     string firstString = currentValue?.ToString();
 199
 200                     // If there's only 1 item, simply call ToString on that
 201                     if (!en.MoveNext())
 202                     {
 203                         // We have to handle the case of either currentValue
 204                         // or its ToString being null
 205                         return firstString ?? string.Empty;
 206                     }
 207
 208                     StringBuilder result = StringBuilderCache.Acquire();
 209
 210                     result.Append(firstString);
 211
 212                     do
 213                     {
 214                         currentValue = en.Current;
 215
 216                         if (currentValue != null)
 217                         {
 218                             result.Append(currentValue.ToString());
 219                         }
 220                     }
 221                     while (en.MoveNext());
 222
 223                     return StringBuilderCache.GetStringAndRelease(result);
 224                 }
 225             }
 226         }
 227
 228         public static string Concat(IEnumerable<string> values)
 229         {
 230             if (values == null)
 231                 throw new ArgumentNullException(nameof(values));
 232
 233             using (IEnumerator<string> en = values.GetEnumerator())
 234             {
 235                 if (!en.MoveNext())
 236                     return string.Empty;
 237
 238                 string firstValue = en.Current;
 239
 240                 if (!en.MoveNext())
 241                 {
 242                     return firstValue ?? string.Empty;
 243                 }
 244
 245                 StringBuilder result = StringBuilderCache.Acquire();
 246                 result.Append(firstValue);
 247
 248                 do
 249                 {
 250                     result.Append(en.Current);
 251                 }
 252                 while (en.MoveNext());
 253
 254                 return StringBuilderCache.GetStringAndRelease(result);
 255             }
 256         }
 257
 258         public static string Concat(string str0, string str1)
 259         {
 260             if (IsNullOrEmpty(str0))
 261             {
 262                 if (IsNullOrEmpty(str1))
 263                 {
 264                     return string.Empty;
 265                 }
 266                 return str1;
 267             }
 268
 269             if (IsNullOrEmpty(str1))
 270             {
 271                 return str0;
 272             }
 273
 274             int str0Length = str0.Length;
 275
 276             string result = FastAllocateString(str0Length + str1.Length);
 277
 278             FillStringChecked(result, 0, str0);
 279             FillStringChecked(result, str0Length, str1);
 280
 281             return result;
 282         }
 283
 284         public static string Concat(string str0, string str1, string str2)
 285         {
 286             if (IsNullOrEmpty(str0))
 287             {
 288                 return Concat(str1, str2);
 289             }
 290
 291             if (IsNullOrEmpty(str1))
 292             {
 293                 return Concat(str0, str2);
 294             }
 295
 296             if (IsNullOrEmpty(str2))
 297             {
 298                 return Concat(str0, str1);
 299             }
 300
 301             int totalLength = str0.Length + str1.Length + str2.Length;
 302
 303             string result = FastAllocateString(totalLength);
 304             FillStringChecked(result, 0, str0);
 305             FillStringChecked(result, str0.Length, str1);
 306             FillStringChecked(result, str0.Length + str1.Length, str2);
 307
 308             return result;
 309         }
 310
 311         public static string Concat(string str0, string str1, string str2, string str3)
 312         {
 313             if (IsNullOrEmpty(str0))
 314             {
 315                 return Concat(str1, str2, str3);
 316             }
 317
 318             if (IsNullOrEmpty(str1))
 319             {
 320                 return Concat(str0, str2, str3);
 321             }
 322
 323             if (IsNullOrEmpty(str2))
 324             {
 325                 return Concat(str0, str1, str3);
 326             }
 327
 328             if (IsNullOrEmpty(str3))
 329             {
 330                 return Concat(str0, str1, str2);
 331             }
 332
 333             int totalLength = str0.Length + str1.Length + str2.Length + str3.Length;
 334
 335             string result = FastAllocateString(totalLength);
 336             FillStringChecked(result, 0, str0);
 337             FillStringChecked(result, str0.Length, str1);
 338             FillStringChecked(result, str0.Length + str1.Length, str2);
 339             FillStringChecked(result, str0.Length + str1.Length + str2.Length, str3);
 340
 341             return result;
 342         }
 343
 344         public static string Concat(params string[] values)
 345         {
 346             if (values == null)
 347                 throw new ArgumentNullException(nameof(values));
 348
 349             if (values.Length <= 1)
 350             {
 351                 return values.Length == 0 ?
 352                     string.Empty :
 353                     values[0] ?? string.Empty;
 354             }
 355
 356             // It's possible that the input values array could be changed concurrently on another
 357             // thread, such that we can't trust that each read of values[i] will be equivalent.
 358             // Worst case, we can make a defensive copy of the array and use that, but we first
 359             // optimistically try the allocation and copies assuming that the array isn't changing,
 360             // which represents the 99.999% case, in particular since string.Concat is used for
 361             // string concatenation by the languages, with the input array being a params array.
 362
 363             // Sum the lengths of all input strings
 364             long totalLengthLong = 0;
 365             for (int i = 0; i < values.Length; i++)
 366             {
 367                 string value = values[i];
 368                 if (value != null)
 369                 {
 370                     totalLengthLong += value.Length;
 371                 }
 372             }
 373
 374             // If it's too long, fail, or if it's empty, return an empty string.
 375             if (totalLengthLong > int.MaxValue)
 376             {
 377                 throw new OutOfMemoryException();
 378             }
 379             int totalLength = (int)totalLengthLong;
 380             if (totalLength == 0)
 381             {
 382                 return string.Empty;
 383             }
 384
 385             // Allocate a new string and copy each input string into it
 386             string result = FastAllocateString(totalLength);
 387             int copiedLength = 0;
 388             for (int i = 0; i < values.Length; i++)
 389             {
 390                 string value = values[i];
 391                 if (!string.IsNullOrEmpty(value))
 392                 {
 393                     int valueLen = value.Length;
 394                     if (valueLen > totalLength - copiedLength)
 395                     {
 396                         copiedLength = -1;
 397                         break;
 398                     }
 399
 400                     FillStringChecked(result, copiedLength, value);
 401                     copiedLength += valueLen;
 402                 }
 403             }
 404
 405             // If we copied exactly the right amount, return the new string.  Otherwise,
 406             // something changed concurrently to mutate the input array: fall back to
 407             // doing the concatenation again, but this time with a defensive copy. This
 408             // fall back should be extremely rare.
 409             return copiedLength == totalLength ? result : Concat((string[])values.Clone());
 410         }
 411
 412         public static string Format(string format, object arg0)
 413         {
 414             return FormatHelper(null, format, new ParamsArray(arg0));
 415         }
 416
 417         public static string Format(string format, object arg0, object arg1)
 418         {
 419             return FormatHelper(null, format, new ParamsArray(arg0, arg1));
 420         }
 421
 422         public static string Format(string format, object arg0, object arg1, object arg2)
 423         {
 424             return FormatHelper(null, format, new ParamsArray(arg0, arg1, arg2));
 425         }
 426
 427         public static string Format(string format, params object[] args)
 428         {
 429             if (args == null)
 430             {
 431                 // To preserve the original exception behavior, throw an exception about format if both
 432                 // args and format are null. The actual null check for format is in FormatHelper.
 433                 throw new ArgumentNullException((format == null) ? nameof(format) : nameof(args));
 434             }
 435
 436             return FormatHelper(null, format, new ParamsArray(args));
 437         }
 438
 439         public static string Format(IFormatProvider provider, string format, object arg0)
 440         {
 441             return FormatHelper(provider, format, new ParamsArray(arg0));
 442         }
 443
 444         public static string Format(IFormatProvider provider, string format, object arg0, object arg1)
 445         {
 446             return FormatHelper(provider, format, new ParamsArray(arg0, arg1));
 447         }
 448
 449         public static string Format(IFormatProvider provider, string format, object arg0, object arg1, object arg2)
 450         {
 451             return FormatHelper(provider, format, new ParamsArray(arg0, arg1, arg2));
 452         }
 453
 454         public static string Format(IFormatProvider provider, string format, params object[] args)
 455         {
 456             if (args == null)
 457             {
 458                 // To preserve the original exception behavior, throw an exception about format if both
 459                 // args and format are null. The actual null check for format is in FormatHelper.
 460                 throw new ArgumentNullException((format == null) ? nameof(format) : nameof(args));
 461             }
 462
 463             return FormatHelper(provider, format, new ParamsArray(args));
 464         }
 465
 466         private static string FormatHelper(IFormatProvider provider, string format, ParamsArray args)
 467         {
 468             if (format == null)
 469                 throw new ArgumentNullException(nameof(format));
 470
 471             return StringBuilderCache.GetStringAndRelease(
 472                 StringBuilderCache
 473                     .Acquire(format.Length + args.Length * 8)
 474                     .AppendFormatHelper(provider, format, args));
 475         }
 476
 477         public string Insert(int startIndex, string value)
 478         {
 479             if (value == null)
 480                 throw new ArgumentNullException(nameof(value));
 481             if (startIndex < 0 || startIndex > this.Length)
 482                 throw new ArgumentOutOfRangeException(nameof(startIndex));
 483
 484             int oldLength = Length;
 485             int insertLength = value.Length;
 486
 487             if (oldLength == 0)
 488                 return value;
 489             if (insertLength == 0)
 490                 return this;
 491
 492             // In case this computation overflows, newLength will be negative and FastAllocateString throws OutOfMemoryException
 493             int newLength = oldLength + insertLength;
 494             string result = FastAllocateString(newLength);
 495             unsafe
 496             {
 497                 fixed (char* srcThis = &_firstChar)
 498                 {
 499                     fixed (char* srcInsert = &value._firstChar)
 500                     {
 501                         fixed (char* dst = &result._firstChar)
 502                         {
 503                             wstrcpy(dst, srcThis, startIndex);
 504                             wstrcpy(dst + startIndex, srcInsert, insertLength);
 505                             wstrcpy(dst + startIndex + insertLength, srcThis + startIndex, oldLength - startIndex);
 506                         }
 507                     }
 508                 }
 509             }
 510             return result;
 511         }
 512
 513         public static string Join(char separator, params string[] value)
 514         {
 515             if (value == null)
 516             {
 517                 throw new ArgumentNullException(nameof(value));
 518             }
 519
 520             return Join(separator, value, 0, value.Length);
 521         }
 522
 523         public static unsafe string Join(char separator, params object[] values)
 524         {
 525             // Defer argument validation to the internal function
 526             return JoinCore(&separator, 1, values);
 527         }
 528
 529         public static unsafe string Join<T>(char separator, IEnumerable<T> values)
 530         {
 531             // Defer argument validation to the internal function
 532             return JoinCore(&separator, 1, values);
 533         }
 534
 535         public static unsafe string Join(char separator, string[] value, int startIndex, int count)
 536         {
 537             // Defer argument validation to the internal function
 538             return JoinCore(&separator, 1, value, startIndex, count);
 539         }
 540
 541         // Joins an array of strings together as one string with a separator between each original string.
 542         //
 543         public static string Join(string separator, params string[] value)
 544         {
 545             if (value == null)
 546             {
 547                 throw new ArgumentNullException(nameof(value));
 548             }
 549             return Join(separator, value, 0, value.Length);
 550         }
 551
 552         public static unsafe string Join(string separator, params object[] values)
 553         {
 554             separator = separator ?? string.Empty;
 555             fixed (char* pSeparator = &separator._firstChar)
 556             {
 557                 // Defer argument validation to the internal function
 558                 return JoinCore(pSeparator, separator.Length, values);
 559             }
 560         }
 561
 562         public static unsafe string Join<T>(string separator, IEnumerable<T> values)
 563         {
 564             separator = separator ?? string.Empty;
 565             fixed (char* pSeparator = &separator._firstChar)
 566             {
 567                 // Defer argument validation to the internal function
 568                 return JoinCore(pSeparator, separator.Length, values);
 569             }
 570         }
 571
 572         public static string Join(string separator, IEnumerable<string> values)
 573         {
 574             if (values == null)
 575             {
 576                 throw new ArgumentNullException(nameof(values));
 577             }
 578
 579             using (IEnumerator<string> en = values.GetEnumerator())
 580             {
 581                 if (!en.MoveNext())
 582                 {
 583                     return string.Empty;
 584                 }
 585
 586                 string firstValue = en.Current;
 587
 588                 if (!en.MoveNext())
 589                 {
 590                     // Only one value available
 591                     return firstValue ?? string.Empty;
 592                 }
 593
 594                 // Null separator and values are handled by the StringBuilder
 595                 StringBuilder result = StringBuilderCache.Acquire();
 596                 result.Append(firstValue);
 597
 598                 do
 599                 {
 600                     result.Append(separator);
 601                     result.Append(en.Current);
 602                 }
 603                 while (en.MoveNext());
 604
 605                 return StringBuilderCache.GetStringAndRelease(result);
 606             }
 607         }
 608
 609         // Joins an array of strings together as one string with a separator between each original string.
 610         //
 611         public static unsafe string Join(string separator, string[] value, int startIndex, int count)
 612         {
 613             separator = separator ?? string.Empty;
 614             fixed (char* pSeparator = &separator._firstChar)
 615             {
 616                 // Defer argument validation to the internal function
 617                 return JoinCore(pSeparator, separator.Length, value, startIndex, count);
 618             }
 619         }
 620
 621         private static unsafe string JoinCore(char* separator, int separatorLength, object[] values)
 622         {
 623             if (values == null)
 624             {
 625                 throw new ArgumentNullException(nameof(values));
 626             }
 627
 628             if (values.Length == 0)
 629             {
 630                 return string.Empty;
 631             }
 632
 633             string firstString = values[0]?.ToString();
 634
 635             if (values.Length == 1)
 636             {
 637                 return firstString ?? string.Empty;
 638             }
 639
 640             StringBuilder result = StringBuilderCache.Acquire();
 641             result.Append(firstString);
 642
 643             for (int i = 1; i < values.Length; i++)
 644             {
 645                 result.Append(separator, separatorLength);
 646                 object value = values[i];
 647                 if (value != null)
 648                 {
 649                     result.Append(value.ToString());
 650                 }
 651             }
 652
 653             return StringBuilderCache.GetStringAndRelease(result);
 654         }
 655
 656         private static unsafe string JoinCore<T>(char* separator, int separatorLength, IEnumerable<T> values)
 657         {
 658             if (values == null)
 659             {
 660                 throw new ArgumentNullException(nameof(values));
 661             }
 662
 663             using (IEnumerator<T> en = values.GetEnumerator())
 664             {
 665                 if (!en.MoveNext())
 666                 {
 667                     return string.Empty;
 668                 }
 669
 670                 // We called MoveNext once, so this will be the first item
 671                 T currentValue = en.Current;
 672
 673                 // Call ToString before calling MoveNext again, since
 674                 // we want to stay consistent with the below loop
 675                 // Everything should be called in the order
 676                 // MoveNext-Current-ToString, unless further optimizations
 677                 // can be made, to avoid breaking changes
 678                 string firstString = currentValue?.ToString();
 679
 680                 // If there's only 1 item, simply call ToString on that
 681                 if (!en.MoveNext())
 682                 {
 683                     // We have to handle the case of either currentValue
 684                     // or its ToString being null
 685                     return firstString ?? string.Empty;
 686                 }
 687
 688                 StringBuilder result = StringBuilderCache.Acquire();
 689
 690                 result.Append(firstString);
 691
 692                 do
 693                 {
 694                     currentValue = en.Current;
 695
 696                     result.Append(separator, separatorLength);
 697                     if (currentValue != null)
 698                     {
 699                         result.Append(currentValue.ToString());
 700                     }
 701                 }
 702                 while (en.MoveNext());
 703
 704                 return StringBuilderCache.GetStringAndRelease(result);
 705             }
 706         }
 707
 708         private static unsafe string JoinCore(char* separator, int separatorLength, string[] value, int startIndex, int count)
 709         {
 710             // If the separator is null, it is converted to an empty string before entering this function.
 711             // Even for empty strings, fixed should never return null (it should return a pointer to a null char).
 712             Debug.Assert(separator != null);
 713             Debug.Assert(separatorLength >= 0);
 714
 715             if (value == null)
 716             {
 717                 throw new ArgumentNullException(nameof(value));
 718             }
 719             if (startIndex < 0)
 720             {
 721                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
 722             }
 723             if (count < 0)
 724             {
 725                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NegativeCount);
 726             }
 727             if (startIndex > value.Length - count)
 728             {
 729                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_IndexCountBuffer);
 730             }
 731
 732             if (count <= 1)
 733             {
 734                 return count == 0 ?
 735                     string.Empty :
 736                     value[startIndex] ?? string.Empty;
 737             }
 738
 739             long totalSeparatorsLength = (long)(count - 1) * separatorLength;
 740             if (totalSeparatorsLength > int.MaxValue)
 741             {
 742                 throw new OutOfMemoryException();
 743             }
 744             int totalLength = (int)totalSeparatorsLength;
 745
 746             // Calculate the length of the resultant string so we know how much space to allocate.
 747             for (int i = startIndex, end = startIndex + count; i < end; i++)
 748             {
 749                 string currentValue = value[i];
 750                 if (currentValue != null)
 751                 {
 752                     totalLength += currentValue.Length;
 753                     if (totalLength < 0) // Check for overflow
 754                     {
 755                         throw new OutOfMemoryException();
 756                     }
 757                 }
 758             }
 759
 760             // Copy each of the strings into the resultant buffer, interleaving with the separator.
 761             string result = FastAllocateString(totalLength);
 762             int copiedLength = 0;
 763
 764             for (int i = startIndex, end = startIndex + count; i < end; i++)
 765             {
 766                 // It's possible that another thread may have mutated the input array
 767                 // such that our second read of an index will not be the same string
 768                 // we got during the first read.
 769
 770                 // We range check again to avoid buffer overflows if this happens.
 771
 772                 string currentValue = value[i];
 773                 if (currentValue != null)
 774                 {
 775                     int valueLen = currentValue.Length;
 776                     if (valueLen > totalLength - copiedLength)
 777                     {
 778                         copiedLength = -1;
 779                         break;
 780                     }
 781
 782                     // Fill in the value.
 783                     FillStringChecked(result, copiedLength, currentValue);
 784                     copiedLength += valueLen;
 785                 }
 786
 787                 if (i < end - 1)
 788                 {
 789                     // Fill in the separator.
 790                     fixed (char* pResult = &result._firstChar)
 791                     {
 792                         // If we are called from the char-based overload, we will not
 793                         // want to call MemoryCopy each time we fill in the separator. So
 794                         // specialize for 1-length separators.
 795                         if (separatorLength == 1)
 796                         {
 797                             pResult[copiedLength] = *separator;
 798                         }
 799                         else
 800                         {
 801                             wstrcpy(pResult + copiedLength, separator, separatorLength);
 802                         }
 803                     }
 804                     copiedLength += separatorLength;
 805                 }
 806             }
 807
 808             // If we copied exactly the right amount, return the new string.  Otherwise,
 809             // something changed concurrently to mutate the input array: fall back to
 810             // doing the concatenation again, but this time with a defensive copy. This
 811             // fall back should be extremely rare.
 812             return copiedLength == totalLength ?
 813                 result :
 814                 JoinCore(separator, separatorLength, (string[])value.Clone(), startIndex, count);
 815         }
 816
 817         public string PadLeft(int totalWidth) => PadLeft(totalWidth, ' ');
 818
 819         public string PadLeft(int totalWidth, char paddingChar)
 820         {
 821             if (totalWidth < 0)
 822                 throw new ArgumentOutOfRangeException(nameof(totalWidth), SR.ArgumentOutOfRange_NeedNonNegNum);
 823             int oldLength = Length;
 824             int count = totalWidth - oldLength;
 825             if (count <= 0)
 826                 return this;
 827             string result = FastAllocateString(totalWidth);
 828             unsafe
 829             {
 830                 fixed (char* dst = &result._firstChar)
 831                 {
 832                     for (int i = 0; i < count; i++)
 833                         dst[i] = paddingChar;
 834                     fixed (char* src = &_firstChar)
 835                     {
 836                         wstrcpy(dst + count, src, oldLength);
 837                     }
 838                 }
 839             }
 840             return result;
 841         }
 842
 843         public string PadRight(int totalWidth) => PadRight(totalWidth, ' ');
 844
 845         public string PadRight(int totalWidth, char paddingChar)
 846         {
 847             if (totalWidth < 0)
 848                 throw new ArgumentOutOfRangeException(nameof(totalWidth), SR.ArgumentOutOfRange_NeedNonNegNum);
 849             int oldLength = Length;
 850             int count = totalWidth - oldLength;
 851             if (count <= 0)
 852                 return this;
 853             string result = FastAllocateString(totalWidth);
 854             unsafe
 855             {
 856                 fixed (char* dst = &result._firstChar)
 857                 {
 858                     fixed (char* src = &_firstChar)
 859                     {
 860                         wstrcpy(dst, src, oldLength);
 861                     }
 862                     for (int i = 0; i < count; i++)
 863                         dst[oldLength + i] = paddingChar;
 864                 }
 865             }
 866             return result;
 867         }
 868
 869         public string Remove(int startIndex, int count)
 870         {
 871             if (startIndex < 0)
 872                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
 873             if (count < 0)
 874                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NegativeCount);
 875             int oldLength = this.Length;
 876             if (count > oldLength - startIndex)
 877                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_IndexCount);
 878
 879             if (count == 0)
 880                 return this;
 881             int newLength = oldLength - count;
 882             if (newLength == 0)
 883                 return string.Empty;
 884
 885             string result = FastAllocateString(newLength);
 886             unsafe
 887             {
 888                 fixed (char* src = &_firstChar)
 889                 {
 890                     fixed (char* dst = &result._firstChar)
 891                     {
 892                         wstrcpy(dst, src, startIndex);
 893                         wstrcpy(dst + startIndex, src + startIndex + count, newLength - startIndex);
 894                     }
 895                 }
 896             }
 897             return result;
 898         }
 899
 900         // a remove that just takes a startindex.
 901         public string Remove(int startIndex)
 902         {
 903             if (startIndex < 0)
 904                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
 905
 906             if (startIndex >= Length)
 907                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndexLessThanLength);
 908
 909             return Substring(0, startIndex);
 910         }
 911
 912         public string Replace(string oldValue, string newValue, bool ignoreCase, CultureInfo culture)
 913         {
 914             return ReplaceCore(oldValue, newValue, culture, ignoreCase ? CompareOptions.IgnoreCase : CompareOptions.None);
 915         }
 916
 917         public string Replace(string oldValue, string newValue, StringComparison comparisonType)
 918         {
 919             switch (comparisonType)
 920             {
 921                 case StringComparison.CurrentCulture:
 922                     return ReplaceCore(oldValue, newValue, CultureInfo.CurrentCulture, CompareOptions.None);
 923
 924                 case StringComparison.CurrentCultureIgnoreCase:
 925                     return ReplaceCore(oldValue, newValue, CultureInfo.CurrentCulture, CompareOptions.IgnoreCase);
 926
 927                 case StringComparison.InvariantCulture:
 928                     return ReplaceCore(oldValue, newValue, CultureInfo.InvariantCulture, CompareOptions.None);
 929
 930                 case StringComparison.InvariantCultureIgnoreCase:
 931                     return ReplaceCore(oldValue, newValue, CultureInfo.InvariantCulture, CompareOptions.IgnoreCase);
 932
 933                 case StringComparison.Ordinal:
 934                     return Replace(oldValue, newValue);
 935
 936                 case StringComparison.OrdinalIgnoreCase:
 937                     return ReplaceCore(oldValue, newValue, CultureInfo.InvariantCulture, CompareOptions.OrdinalIgnoreCase);
 938
 939                 default:
 940                     throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType));
 941             }
 942         }
 943
 944         private unsafe string ReplaceCore(string oldValue, string newValue, CultureInfo culture, CompareOptions options)
 945         {
 946             if (oldValue == null)
 947                 throw new ArgumentNullException(nameof(oldValue));
 948             if (oldValue.Length == 0)
 949                 throw new ArgumentException(SR.Argument_StringZeroLength, nameof(oldValue));
 950
 951             // If they asked to replace oldValue with a null, replace all occurrences
 952             // with the empty string.
 953             if (newValue == null)
 954                 newValue = string.Empty;
 955
 956             CultureInfo referenceCulture = culture ?? CultureInfo.CurrentCulture;
 957             StringBuilder result = StringBuilderCache.Acquire();
 958
 959             int startIndex = 0;
 960             int index = 0;
 961
 962             int matchLength = 0;
 963
 964             bool hasDoneAnyReplacements = false;
 965             CompareInfo ci = referenceCulture.CompareInfo;
 966
 967             do
 968             {
 969                 index = ci.IndexOf(this, oldValue, startIndex, this.Length - startIndex, options, &matchLength);
 970                 if (index >= 0)
 971                 {
 972                     // append the unmodified portion of string
 973                     result.Append(this, startIndex, index - startIndex);
 974
 975                     // append the replacement
 976                     result.Append(newValue);
 977
 978                     startIndex = index + matchLength;
 979                     hasDoneAnyReplacements = true;
 980                 }
 981                 else if (!hasDoneAnyReplacements)
 982                 {
 983                     // small optimization,
 984                     // if we have not done any replacements,
 985                     // we will return the original string
 986                     StringBuilderCache.Release(result);
 987                     return this;
 988                 }
 989                 else
 990                 {
 991                     result.Append(this, startIndex, this.Length - startIndex);
 992                 }
 993             } while (index >= 0);
 994
 995             return StringBuilderCache.GetStringAndRelease(result);
 996         }
 997
 998         // Replaces all instances of oldChar with newChar.
 999         //
1000         public string Replace(char oldChar, char newChar)
1001         {
1002             if (oldChar == newChar)
1003                 return this;
1004
1005             unsafe
1006             {
1007                 int remainingLength = Length;
1008
1009                 fixed (char* pChars = &_firstChar)
1010                 {
1011                     char* pSrc = pChars;
1012
1013                     while (remainingLength > 0)
1014                     {
1015                         if (*pSrc == oldChar)
1016                         {
1017                             break;
1018                         }
1019
1020                         remainingLength--;
1021                         pSrc++;
1022                     }
1023                 }
1024
1025                 if (remainingLength == 0)
1026                     return this;
1027
1028                 string result = FastAllocateString(Length);
1029
1030                 fixed (char* pChars = &_firstChar)
1031                 {
1032                     fixed (char* pResult = &result._firstChar)
1033                     {
1034                         int copyLength = Length - remainingLength;
1035
1036                         //Copy the characters already proven not to match.
1037                         if (copyLength > 0)
1038                         {
1039                             wstrcpy(pResult, pChars, copyLength);
1040                         }
1041
1042                         //Copy the remaining characters, doing the replacement as we go.
1043                         char* pSrc = pChars + copyLength;
1044                         char* pDst = pResult + copyLength;
1045
1046                         do
1047                         {
1048                             char currentChar = *pSrc;
1049                             if (currentChar == oldChar)
1050                                 currentChar = newChar;
1051                             *pDst = currentChar;
1052
1053                             remainingLength--;
1054                             pSrc++;
1055                             pDst++;
1056                         } while (remainingLength > 0);
1057                     }
1058                 }
1059
1060                 return result;
1061             }
1062         }
1063
1064         public string Replace(string oldValue, string newValue)
1065         {
1066             if (oldValue == null)
1067                 throw new ArgumentNullException(nameof(oldValue));
1068             if (oldValue.Length == 0)
1069                 throw new ArgumentException(SR.Argument_StringZeroLength, nameof(oldValue));
1070
1071             // Api behavior: if newValue is null, instances of oldValue are to be removed.
1072             if (newValue == null)
1073                 newValue = string.Empty;
1074
1075             Span<int> initialSpan = stackalloc int[StackallocIntBufferSizeLimit];
1076             var replacementIndices = new ValueListBuilder<int>(initialSpan);
1077
1078             unsafe
1079             {
1080                 fixed (char* pThis = &_firstChar)
1081                 {
1082                     int matchIdx = 0;
1083                     int lastPossibleMatchIdx = this.Length - oldValue.Length;
1084                     while (matchIdx <= lastPossibleMatchIdx)
1085                     {
1086                         char* pMatch = pThis + matchIdx;
1087                         for (int probeIdx = 0; probeIdx < oldValue.Length; probeIdx++)
1088                         {
1089                             if (pMatch[probeIdx] != oldValue[probeIdx])
1090                             {
1091                                 goto Next;
1092                             }
1093                         }
1094                         // Found a match for the string. Record the location of the match and skip over the "oldValue."
1095                         replacementIndices.Append(matchIdx);
1096                         matchIdx += oldValue.Length;
1097                         continue;
1098
1099                     Next:
1100                         matchIdx++;
1101                     }
1102                 }
1103             }
1104
1105             if (replacementIndices.Length == 0)
1106                 return this;
1107
1108             // String allocation and copying is in separate method to make this method faster for the case where
1109             // nothing needs replacing.
1110             string dst = ReplaceHelper(oldValue.Length, newValue, replacementIndices.AsSpan());
1111
1112             replacementIndices.Dispose();
1113
1114             return dst;
1115         }
1116
1117         private string ReplaceHelper(int oldValueLength, string newValue, ReadOnlySpan<int> indices)
1118         {
1119             Debug.Assert(indices.Length > 0);
1120
1121             long dstLength = this.Length + ((long)(newValue.Length - oldValueLength)) * indices.Length;
1122             if (dstLength > int.MaxValue)
1123                 throw new OutOfMemoryException();
1124             string dst = FastAllocateString((int)dstLength);
1125
1126             Span<char> dstSpan = new Span<char>(ref dst.GetRawStringData(), dst.Length);
1127
1128             int thisIdx = 0;
1129             int dstIdx = 0;
1130
1131             for (int r = 0; r < indices.Length; r++)
1132             {
1133                 int replacementIdx = indices[r];
1134
1135                 // Copy over the non-matching portion of the original that precedes this occurrence of oldValue.
1136                 int count = replacementIdx - thisIdx;
1137                 if (count != 0)
1138                 {
1139                     this.AsSpan().Slice(thisIdx, count).CopyTo(dstSpan.Slice(dstIdx));
1140                     dstIdx += count;
1141                 }
1142                 thisIdx = replacementIdx + oldValueLength;
1143
1144                 // Copy over newValue to replace the oldValue.
1145                 newValue.AsSpan().CopyTo(dstSpan.Slice(dstIdx));
1146                 dstIdx += newValue.Length;
1147             }
1148
1149             // Copy over the final non-matching portion at the end of the string.
1150             Debug.Assert(this.Length - thisIdx == dstSpan.Length - dstIdx);
1151             this.AsSpan().Slice(thisIdx).CopyTo(dstSpan.Slice(dstIdx));
1152
1153             return dst;
1154         }
1155
1156         public string[] Split(char separator, StringSplitOptions options = StringSplitOptions.None)
1157         {
1158             return SplitInternal(new ReadOnlySpan<char>(ref separator, 1), int.MaxValue, options);
1159         }
1160
1161         public string[] Split(char separator, int count, StringSplitOptions options = StringSplitOptions.None)
1162         {
1163             return SplitInternal(new ReadOnlySpan<char>(ref separator, 1), count, options);
1164         }
1165
1166         // Creates an array of strings by splitting this string at each
1167         // occurrence of a separator.  The separator is searched for, and if found,
1168         // the substring preceding the occurrence is stored as the first element in
1169         // the array of strings.  We then continue in this manner by searching
1170         // the substring that follows the occurrence.  On the other hand, if the separator
1171         // is not found, the array of strings will contain this instance as its only element.
1172         // If the separator is null
1173         // whitespace (i.e., Character.IsWhitespace) is used as the separator.
1174         //
1175         public string[] Split(params char[] separator)
1176         {
1177             return SplitInternal(separator, int.MaxValue, StringSplitOptions.None);
1178         }
1179
1180         // Creates an array of strings by splitting this string at each
1181         // occurrence of a separator.  The separator is searched for, and if found,
1182         // the substring preceding the occurrence is stored as the first element in
1183         // the array of strings.  We then continue in this manner by searching
1184         // the substring that follows the occurrence.  On the other hand, if the separator
1185         // is not found, the array of strings will contain this instance as its only element.
1186         // If the separator is the empty string (i.e., string.Empty), then
1187         // whitespace (i.e., Character.IsWhitespace) is used as the separator.
1188         // If there are more than count different strings, the last n-(count-1)
1189         // elements are concatenated and added as the last string.
1190         //
1191         public string[] Split(char[] separator, int count)
1192         {
1193             return SplitInternal(separator, count, StringSplitOptions.None);
1194         }
1195
1196         public string[] Split(char[] separator, StringSplitOptions options)
1197         {
1198             return SplitInternal(separator, int.MaxValue, options);
1199         }
1200
1201         public string[] Split(char[] separator, int count, StringSplitOptions options)
1202         {
1203             return SplitInternal(separator, count, options);
1204         }
1205
1206         private string[] SplitInternal(ReadOnlySpan<char> separators, int count, StringSplitOptions options)
1207         {
1208             if (count < 0)
1209                 throw new ArgumentOutOfRangeException(nameof(count),
1210                     SR.ArgumentOutOfRange_NegativeCount);
1211
1212             if (options < StringSplitOptions.None || options > StringSplitOptions.RemoveEmptyEntries)
1213                 throw new ArgumentException(SR.Format(SR.Arg_EnumIllegalVal, options));
1214
1215             bool omitEmptyEntries = (options == StringSplitOptions.RemoveEmptyEntries);
1216
1217             if ((count == 0) || (omitEmptyEntries && Length == 0))
1218             {
1219                 return Array.Empty<string>();
1220             }
1221
1222             if (count == 1)
1223             {
1224                 return new string[] { this };
1225             }
1226
1227             Span<int> initialSpan = stackalloc int[StackallocIntBufferSizeLimit];
1228             var sepListBuilder = new ValueListBuilder<int>(initialSpan);
1229
1230             MakeSeparatorList(separators, ref sepListBuilder);
1231             ReadOnlySpan<int> sepList = sepListBuilder.AsSpan();
1232
1233             // Handle the special case of no replaces.
1234             if (sepList.Length == 0)
1235             {
1236                 return new string[] { this };
1237             }
1238
1239             string[] result = omitEmptyEntries
1240                 ? SplitOmitEmptyEntries(sepList, default, 1, count)
1241                 : SplitKeepEmptyEntries(sepList, default, 1, count);
1242
1243             sepListBuilder.Dispose();
1244
1245             return result;
1246         }
1247
1248         public string[] Split(string separator, StringSplitOptions options = StringSplitOptions.None)
1249         {
1250             return SplitInternal(separator ?? string.Empty, null, int.MaxValue, options);
1251         }
1252
1253         public string[] Split(string separator, Int32 count, StringSplitOptions options = StringSplitOptions.None)
1254         {
1255             return SplitInternal(separator ?? string.Empty, null, count, options);
1256         }
1257
1258         public string[] Split(string[] separator, StringSplitOptions options)
1259         {
1260             return SplitInternal(null, separator, int.MaxValue, options);
1261         }
1262
1263         public string[] Split(string[] separator, Int32 count, StringSplitOptions options)
1264         {
1265             return SplitInternal(null, separator, count, options);
1266         }
1267
1268         private string[] SplitInternal(string separator, string[] separators, int count, StringSplitOptions options)
1269         {
1270             if (count < 0)
1271             {
1272                 throw new ArgumentOutOfRangeException(nameof(count),
1273                     SR.ArgumentOutOfRange_NegativeCount);
1274             }
1275
1276             if (options < StringSplitOptions.None || options > StringSplitOptions.RemoveEmptyEntries)
1277             {
1278                 throw new ArgumentException(SR.Format(SR.Arg_EnumIllegalVal, (int)options));
1279             }
1280
1281             bool omitEmptyEntries = (options == StringSplitOptions.RemoveEmptyEntries);
1282
1283             bool singleSeparator = separator != null;
1284
1285             if (!singleSeparator && (separators == null || separators.Length == 0))
1286             {
1287                 return SplitInternal((char[])null, count, options);
1288             }
1289
1290             if ((count == 0) || (omitEmptyEntries && Length == 0))
1291             {
1292                 return Array.Empty<string>();
1293             }
1294
1295             if (count == 1 || (singleSeparator && separator.Length == 0))
1296             {
1297                 return new string[] { this };
1298             }
1299
1300             if (singleSeparator)
1301             {
1302                 return SplitInternal(separator, count, options);
1303             }
1304
1305             Span<int> sepListInitialSpan = stackalloc int[StackallocIntBufferSizeLimit];
1306             var sepListBuilder = new ValueListBuilder<int>(sepListInitialSpan);
1307
1308             Span<int> lengthListInitialSpan = stackalloc int[StackallocIntBufferSizeLimit];
1309             var lengthListBuilder = new ValueListBuilder<int>(lengthListInitialSpan);
1310
1311             MakeSeparatorList(separators, ref sepListBuilder, ref lengthListBuilder);
1312             ReadOnlySpan<int> sepList = sepListBuilder.AsSpan();
1313             ReadOnlySpan<int> lengthList = lengthListBuilder.AsSpan();
1314
1315             // Handle the special case of no replaces.
1316             if (sepList.Length == 0)
1317             {
1318                 return new string[] { this };
1319             }
1320
1321             string[] result = omitEmptyEntries
1322                 ? SplitOmitEmptyEntries(sepList, lengthList, 0, count)
1323                 : SplitKeepEmptyEntries(sepList, lengthList, 0, count);
1324
1325             sepListBuilder.Dispose();
1326             lengthListBuilder.Dispose();
1327
1328             return result;
1329         }
1330
1331         private string[] SplitInternal(string separator, int count, StringSplitOptions options)
1332         {
1333             Span<int> sepListInitialSpan = stackalloc int[StackallocIntBufferSizeLimit];
1334             var sepListBuilder = new ValueListBuilder<int>(sepListInitialSpan);
1335
1336             MakeSeparatorList(separator, ref sepListBuilder);
1337             ReadOnlySpan<int> sepList = sepListBuilder.AsSpan();
1338             if (sepList.Length == 0)
1339             {
1340                 // there are no separators so sepListBuilder did not rent an array from pool and there is no need to dispose it
1341                 return new string[] { this };
1342             }
1343
1344             string[] result = options == StringSplitOptions.RemoveEmptyEntries
1345                 ? SplitOmitEmptyEntries(sepList, default, separator.Length, count)
1346                 : SplitKeepEmptyEntries(sepList, default, separator.Length, count);
1347
1348             sepListBuilder.Dispose();
1349
1350             return result;
1351         }
1352
1353         private string[] SplitKeepEmptyEntries(ReadOnlySpan<int> sepList, ReadOnlySpan<int> lengthList, int defaultLength, int count)
1354         {
1355             Debug.Assert(count >= 2);
1356
1357             int currIndex = 0;
1358             int arrIndex = 0;
1359
1360             count--;
1361             int numActualReplaces = (sepList.Length < count) ? sepList.Length : count;
1362
1363             //Allocate space for the new array.
1364             //+1 for the string from the end of the last replace to the end of the string.
1365             string[] splitStrings = new string[numActualReplaces + 1];
1366
1367             for (int i = 0; i < numActualReplaces && currIndex < Length; i++)
1368             {
1369                 splitStrings[arrIndex++] = Substring(currIndex, sepList[i] - currIndex);
1370                 currIndex = sepList[i] + (lengthList.IsEmpty ? defaultLength : lengthList[i]);
1371             }
1372
1373             //Handle the last string at the end of the array if there is one.
1374             if (currIndex < Length && numActualReplaces >= 0)
1375             {
1376                 splitStrings[arrIndex] = Substring(currIndex);
1377             }
1378             else if (arrIndex == numActualReplaces)
1379             {
1380                 //We had a separator character at the end of a string.  Rather than just allowing
1381                 //a null character, we'll replace the last element in the array with an empty string.
1382                 splitStrings[arrIndex] = string.Empty;
1383             }
1384
1385             return splitStrings;
1386         }
1387
1388
1389         // This function will not keep the Empty string
1390         private string[] SplitOmitEmptyEntries(ReadOnlySpan<int> sepList, ReadOnlySpan<int> lengthList, int defaultLength, int count)
1391         {
1392             Debug.Assert(count >= 2);
1393
1394             int numReplaces = sepList.Length;
1395
1396             // Allocate array to hold items. This array may not be
1397             // filled completely in this function, we will create a
1398             // new array and copy string references to that new array.
1399             int maxItems = (numReplaces < count) ? (numReplaces + 1) : count;
1400             string[] splitStrings = new string[maxItems];
1401
1402             int currIndex = 0;
1403             int arrIndex = 0;
1404
1405             for (int i = 0; i < numReplaces && currIndex < Length; i++)
1406             {
1407                 if (sepList[i] - currIndex > 0)
1408                 {
1409                     splitStrings[arrIndex++] = Substring(currIndex, sepList[i] - currIndex);
1410                 }
1411                 currIndex = sepList[i] + (lengthList.IsEmpty ? defaultLength : lengthList[i]);
1412                 if (arrIndex == count - 1)
1413                 {
1414                     // If all the remaining entries at the end are empty, skip them
1415                     while (i < numReplaces - 1 && currIndex == sepList[++i])
1416                     {
1417                         currIndex += (lengthList.IsEmpty ? defaultLength : lengthList[i]);
1418                     }
1419                     break;
1420                 }
1421             }
1422
1423             // we must have at least one slot left to fill in the last string.
1424             Debug.Assert(arrIndex < maxItems);
1425
1426             //Handle the last string at the end of the array if there is one.
1427             if (currIndex < Length)
1428             {
1429                 splitStrings[arrIndex++] = Substring(currIndex);
1430             }
1431
1432             string[] stringArray = splitStrings;
1433             if (arrIndex != maxItems)
1434             {
1435                 stringArray = new string[arrIndex];
1436                 for (int j = 0; j < arrIndex; j++)
1437                 {
1438                     stringArray[j] = splitStrings[j];
1439                 }
1440             }
1441             return stringArray;
1442         }
1443
1444         /// <summary>
1445         /// Uses ValueListBuilder to create list that holds indexes of separators in string.
1446         /// </summary>
1447         /// <param name="separators"><see cref="ReadOnlySpan{T}"/> of separator chars</param>
1448         /// <param name="sepListBuilder"><see cref="ValueListBuilder{T}"/> to store indexes</param>
1449         /// <returns></returns>
1450         private void MakeSeparatorList(ReadOnlySpan<char> separators, ref ValueListBuilder<int> sepListBuilder)
1451         {
1452             char sep0, sep1, sep2;
1453
1454             switch (separators.Length)
1455             {
1456                 // Special-case no separators to mean any whitespace is a separator.
1457                 case 0:
1458                     for (int i = 0; i < Length; i++)
1459                     {
1460                         if (char.IsWhiteSpace(this[i]))
1461                         {
1462                             sepListBuilder.Append(i);
1463                         }
1464                     }
1465                     break;
1466
1467                 // Special-case the common cases of 1, 2, and 3 separators, with manual comparisons against each separator.
1468                 case 1:
1469                     sep0 = separators[0];
1470                     for (int i = 0; i < Length; i++)
1471                     {
1472                         if (this[i] == sep0)
1473                         {
1474                             sepListBuilder.Append(i);
1475                         }
1476                     }
1477                     break;
1478                 case 2:
1479                     sep0 = separators[0];
1480                     sep1 = separators[1];
1481                     for (int i = 0; i < Length; i++)
1482                     {
1483                         char c = this[i];
1484                         if (c == sep0 || c == sep1)
1485                         {
1486                             sepListBuilder.Append(i);
1487                         }
1488                     }
1489                     break;
1490                 case 3:
1491                     sep0 = separators[0];
1492                     sep1 = separators[1];
1493                     sep2 = separators[2];
1494                     for (int i = 0; i < Length; i++)
1495                     {
1496                         char c = this[i];
1497                         if (c == sep0 || c == sep1 || c == sep2)
1498                         {
1499                             sepListBuilder.Append(i);
1500                         }
1501                     }
1502                     break;
1503
1504                 // Handle > 3 separators with a probabilistic map, ala IndexOfAny.
1505                 // This optimizes for chars being unlikely to match a separator.
1506                 default:
1507                     unsafe
1508                     {
1509                         ProbabilisticMap map = default;
1510                         uint* charMap = (uint*)&map;
1511                         InitializeProbabilisticMap(charMap, separators);
1512
1513                         for (int i = 0; i < Length; i++)
1514                         {
1515                             char c = this[i];
1516                             if (IsCharBitSet(charMap, (byte)c) && IsCharBitSet(charMap, (byte)(c >> 8)) &&
1517                                 separators.Contains(c))
1518                             {
1519                                 sepListBuilder.Append(i);
1520                             }
1521                         }
1522                     }
1523                     break;
1524             }
1525         }
1526
1527         /// <summary>
1528         /// Uses ValueListBuilder to create list that holds indexes of separators in string.
1529         /// </summary>
1530         /// <param name="separator">separator string</param>
1531         /// <param name="sepListBuilder"><see cref="ValueListBuilder{T}"/> to store indexes</param>
1532         /// <returns></returns>
1533         private void MakeSeparatorList(string separator, ref ValueListBuilder<int> sepListBuilder)
1534         {
1535             Debug.Assert(!IsNullOrEmpty(separator), "!string.IsNullOrEmpty(separator)");
1536
1537             int currentSepLength = separator.Length;
1538
1539             for (int i = 0; i < Length; i++)
1540             {
1541                 if (this[i] == separator[0] && currentSepLength <= Length - i)
1542                 {
1543                     if (currentSepLength == 1
1544                         || CompareOrdinal(this, i, separator, 0, currentSepLength) == 0)
1545                     {
1546                         sepListBuilder.Append(i);
1547                         i += currentSepLength - 1;
1548                     }
1549                 }
1550             }
1551         }
1552
1553         /// <summary>
1554         /// Uses ValueListBuilder to create list that holds indexes of separators in string and list that holds length of separator strings.
1555         /// </summary>
1556         /// <param name="separators">separator strngs</param>
1557         /// <param name="sepListBuilder"><see cref="ValueListBuilder{T}"/> for separator indexes</param>
1558         /// <param name="lengthListBuilder"><see cref="ValueListBuilder{T}"/> for separator length values</param>
1559         private void MakeSeparatorList(string[] separators, ref ValueListBuilder<int> sepListBuilder, ref ValueListBuilder<int> lengthListBuilder)
1560         {
1561             Debug.Assert(separators != null && separators.Length > 0, "separators != null && separators.Length > 0");
1562
1563             int sepCount = separators.Length;
1564
1565             for (int i = 0; i < Length; i++)
1566             {
1567                 for (int j = 0; j < separators.Length; j++)
1568                 {
1569                     string separator = separators[j];
1570                     if (IsNullOrEmpty(separator))
1571                     {
1572                         continue;
1573                     }
1574                     int currentSepLength = separator.Length;
1575                     if (this[i] == separator[0] && currentSepLength <= Length - i)
1576                     {
1577                         if (currentSepLength == 1
1578                             || CompareOrdinal(this, i, separator, 0, currentSepLength) == 0)
1579                         {
1580                             sepListBuilder.Append(i);
1581                             lengthListBuilder.Append(currentSepLength);
1582                             i += currentSepLength - 1;
1583                             break;
1584                         }
1585                     }
1586                 }
1587             }
1588         }
1589
1590         // Returns a substring of this string.
1591         //
1592         public string Substring(int startIndex) => Substring(startIndex, Length - startIndex);
1593
1594         public string Substring(int startIndex, int length)
1595         {
1596             if (startIndex < 0)
1597             {
1598                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
1599             }
1600
1601             if (startIndex > Length)
1602             {
1603                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndexLargerThanLength);
1604             }
1605
1606             if (length < 0)
1607             {
1608                 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_NegativeLength);
1609             }
1610
1611             if (startIndex > Length - length)
1612             {
1613                 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_IndexLength);
1614             }
1615
1616             if (length == 0)
1617             {
1618                 return string.Empty;
1619             }
1620
1621             if (startIndex == 0 && length == this.Length)
1622             {
1623                 return this;
1624             }
1625
1626             return InternalSubString(startIndex, length);
1627         }
1628
1629         private unsafe string InternalSubString(int startIndex, int length)
1630         {
1631             Debug.Assert(startIndex >= 0 && startIndex <= this.Length, "StartIndex is out of range!");
1632             Debug.Assert(length >= 0 && startIndex <= this.Length - length, "length is out of range!");
1633
1634             string result = FastAllocateString(length);
1635
1636             fixed (char* dest = &result._firstChar)
1637             fixed (char* src = &_firstChar)
1638             {
1639                 wstrcpy(dest, src + startIndex, length);
1640             }
1641
1642             return result;
1643         }
1644
1645         // Creates a copy of this string in lower case.  The culture is set by culture.
1646         public string ToLower()
1647         {
1648             return CultureInfo.CurrentCulture.TextInfo.ToLower(this);
1649         }
1650
1651         // Creates a copy of this string in lower case.  The culture is set by culture.
1652         public string ToLower(CultureInfo culture)
1653         {
1654             if (culture == null)
1655             {
1656                 throw new ArgumentNullException(nameof(culture));
1657             }
1658             return culture.TextInfo.ToLower(this);
1659         }
1660
1661         // Creates a copy of this string in lower case based on invariant culture.
1662         public string ToLowerInvariant()
1663         {
1664             return CultureInfo.InvariantCulture.TextInfo.ToLower(this);
1665         }
1666
1667         public string ToUpper()
1668         {
1669             return CultureInfo.CurrentCulture.TextInfo.ToUpper(this);
1670         }
1671
1672         // Creates a copy of this string in upper case.  The culture is set by culture.
1673         public string ToUpper(CultureInfo culture)
1674         {
1675             if (culture == null)
1676             {
1677                 throw new ArgumentNullException(nameof(culture));
1678             }
1679             return culture.TextInfo.ToUpper(this);
1680         }
1681
1682         //Creates a copy of this string in upper case based on invariant culture.
1683         public string ToUpperInvariant()
1684         {
1685             return CultureInfo.InvariantCulture.TextInfo.ToUpper(this);
1686         }
1687
1688         // Trims the whitespace from both ends of the string.  Whitespace is defined by
1689         // Char.IsWhiteSpace.
1690         //
1691         public string Trim() => TrimWhiteSpaceHelper(TrimType.Both);
1692
1693         // Removes a set of characters from the beginning and end of this string.
1694         public unsafe string Trim(char trimChar) => TrimHelper(&trimChar, 1, TrimType.Both);
1695
1696         // Removes a set of characters from the beginning and end of this string.
1697         public unsafe string Trim(params char[] trimChars)
1698         {
1699             if (trimChars == null || trimChars.Length == 0)
1700             {
1701                 return TrimWhiteSpaceHelper(TrimType.Both);
1702             }
1703             fixed (char* pTrimChars = &trimChars[0])
1704             {
1705                 return TrimHelper(pTrimChars, trimChars.Length, TrimType.Both);
1706             }
1707         }
1708
1709         // Removes a set of characters from the beginning of this string.
1710         public string TrimStart() => TrimWhiteSpaceHelper(TrimType.Head);
1711
1712         // Removes a set of characters from the beginning of this string.
1713         public unsafe string TrimStart(char trimChar) => TrimHelper(&trimChar, 1, TrimType.Head);
1714
1715         // Removes a set of characters from the beginning of this string.
1716         public unsafe string TrimStart(params char[] trimChars)
1717         {
1718             if (trimChars == null || trimChars.Length == 0)
1719             {
1720                 return TrimWhiteSpaceHelper(TrimType.Head);
1721             }
1722             fixed (char* pTrimChars = &trimChars[0])
1723             {
1724                 return TrimHelper(pTrimChars, trimChars.Length, TrimType.Head);
1725             }
1726         }
1727
1728         // Removes a set of characters from the end of this string.
1729         public string TrimEnd() => TrimWhiteSpaceHelper(TrimType.Tail);
1730
1731         // Removes a set of characters from the end of this string.
1732         public unsafe string TrimEnd(char trimChar) => TrimHelper(&trimChar, 1, TrimType.Tail);
1733
1734         // Removes a set of characters from the end of this string.
1735         public unsafe string TrimEnd(params char[] trimChars)
1736         {
1737             if (trimChars == null || trimChars.Length == 0)
1738             {
1739                 return TrimWhiteSpaceHelper(TrimType.Tail);
1740             }
1741             fixed (char* pTrimChars = &trimChars[0])
1742             {
1743                 return TrimHelper(pTrimChars, trimChars.Length, TrimType.Tail);
1744             }
1745         }
1746
1747         private string TrimWhiteSpaceHelper(TrimType trimType)
1748         {
1749             // end will point to the first non-trimmed character on the right.
1750             // start will point to the first non-trimmed character on the left.
1751             int end = Length - 1;
1752             int start = 0;
1753
1754             // Trim specified characters.
1755             if (trimType != TrimType.Tail)
1756             {
1757                 for (start = 0; start < Length; start++)
1758                 {
1759                     if (!char.IsWhiteSpace(this[start]))
1760                     {
1761                         break;
1762                     }
1763                 }
1764             }
1765
1766             if (trimType != TrimType.Head)
1767             {
1768                 for (end = Length - 1; end >= start; end--)
1769                 {
1770                     if (!char.IsWhiteSpace(this[end]))
1771                     {
1772                         break;
1773                     }
1774                 }
1775             }
1776
1777             return CreateTrimmedString(start, end);
1778         }
1779
1780         private unsafe string TrimHelper(char* trimChars, int trimCharsLength, TrimType trimType)
1781         {
1782             Debug.Assert(trimChars != null);
1783             Debug.Assert(trimCharsLength > 0);
1784
1785             // end will point to the first non-trimmed character on the right.
1786             // start will point to the first non-trimmed character on the left.
1787             int end = Length - 1;
1788             int start = 0;
1789
1790             // Trim specified characters.
1791             if (trimType != TrimType.Tail)
1792             {
1793                 for (start = 0; start < Length; start++)
1794                 {
1795                     int i = 0;
1796                     char ch = this[start];
1797                     for (i = 0; i < trimCharsLength; i++)
1798                     {
1799                         if (trimChars[i] == ch)
1800                         {
1801                             break;
1802                         }
1803                     }
1804                     if (i == trimCharsLength)
1805                     {
1806                         // The character is not in trimChars, so stop trimming.
1807                         break;
1808                     }
1809                 }
1810             }
1811
1812             if (trimType != TrimType.Head)
1813             {
1814                 for (end = Length - 1; end >= start; end--)
1815                 {
1816                     int i = 0;
1817                     char ch = this[end];
1818                     for (i = 0; i < trimCharsLength; i++)
1819                     {
1820                         if (trimChars[i] == ch)
1821                         {
1822                             break;
1823                         }
1824                     }
1825                     if (i == trimCharsLength)
1826                     {
1827                         // The character is not in trimChars, so stop trimming.
1828                         break;
1829                     }
1830                 }
1831             }
1832
1833             return CreateTrimmedString(start, end);
1834         }
1835
1836         private string CreateTrimmedString(int start, int end)
1837         {
1838             int len = end - start + 1;
1839             return
1840                 len == Length ? this :
1841                 len == 0 ? string.Empty :
1842                 InternalSubString(start, len);
1843         }
1844
1845         private enum TrimType
1846         {
1847             Head = 0,
1848             Tail = 1,
1849             Both = 2
1850         }
1851     }
1852 }