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.
7 using System.Runtime.Serialization;
9 using System.Runtime.CompilerServices;
10 using System.Runtime.InteropServices;
11 using System.Runtime.Versioning;
12 using System.Security;
13 using System.Threading;
14 using System.Globalization;
15 using System.Diagnostics;
16 using System.Collections.Generic;
20 // This class represents a mutable string. It is convenient for situations in
21 // which it is desirable to modify a string, perhaps by removing, replacing, or
22 // inserting characters, without creating a new String subsequent to
25 // The methods contained within this class do not return a new StringBuilder
26 // object unless specified otherwise. This class may be used in conjunction with the String
27 // class to carry out modifications upon strings.
29 [System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
30 public sealed partial class StringBuilder : ISerializable
32 // A StringBuilder is internally represented as a linked list of blocks each of which holds
33 // a chunk of the string. It turns out string as a whole can also be represented as just a chunk,
34 // so that is what we do.
37 /// The character buffer for this chunk.
39 internal char[] m_ChunkChars;
42 /// The chunk that logically precedes this chunk.
44 internal StringBuilder m_ChunkPrevious;
47 /// The number of characters in this chunk.
48 /// This is the number of elements in <see cref="m_ChunkChars"/> that are in use, from the start of the buffer.
50 internal int m_ChunkLength;
53 /// The logical offset of this chunk's characters in the string it is a part of.
54 /// This is the sum of the number of characters in preceding blocks.
56 internal int m_ChunkOffset;
59 /// The maximum capacity this builder is allowed to have.
61 internal int m_MaxCapacity;
64 /// The default capacity of a <see cref="StringBuilder"/>.
66 internal const int DefaultCapacity = 16;
68 private const string CapacityField = "Capacity"; // Do not rename (binary serialization)
69 private const string MaxCapacityField = "m_MaxCapacity"; // Do not rename (binary serialization)
70 private const string StringValueField = "m_StringValue"; // Do not rename (binary serialization)
71 private const string ThreadIDField = "m_currentThread"; // Do not rename (binary serialization)
73 // We want to keep chunk arrays out of large object heap (< 85K bytes ~ 40K chars) to be sure.
74 // Making the maximum chunk size big means less allocation code called, but also more waste
75 // in unused characters and slower inserts / replaces (since you do need to slide characters over
77 internal const int MaxChunkSize = 8000;
80 /// Initializes a new instance of the <see cref="StringBuilder"/> class.
82 public StringBuilder()
84 m_MaxCapacity = int.MaxValue;
85 m_ChunkChars = new char[DefaultCapacity];
89 /// Initializes a new instance of the <see cref="StringBuilder"/> class.
91 /// <param name="capacity">The initial capacity of this builder.</param>
92 public StringBuilder(int capacity)
93 : this(capacity, int.MaxValue)
98 /// Initializes a new instance of the <see cref="StringBuilder"/> class.
100 /// <param name="value">The initial contents of this builder.</param>
101 public StringBuilder(string value)
102 : this(value, DefaultCapacity)
107 /// Initializes a new instance of the <see cref="StringBuilder"/> class.
109 /// <param name="value">The initial contents of this builder.</param>
110 /// <param name="capacity">The initial capacity of this builder.</param>
111 public StringBuilder(string value, int capacity)
112 : this(value, 0, value?.Length ?? 0, capacity)
117 /// Initializes a new instance of the <see cref="StringBuilder"/> class.
119 /// <param name="value">The initial contents of this builder.</param>
120 /// <param name="startIndex">The index to start in <paramref name="value"/>.</param>
121 /// <param name="length">The number of characters to read in <paramref name="value"/>.</param>
122 /// <param name="capacity">The initial capacity of this builder.</param>
123 public StringBuilder(string value, int startIndex, int length, int capacity)
127 throw new ArgumentOutOfRangeException(nameof(capacity), SR.Format(SR.ArgumentOutOfRange_MustBePositive, nameof(capacity)));
131 throw new ArgumentOutOfRangeException(nameof(length), SR.Format(SR.ArgumentOutOfRange_MustBeNonNegNum, nameof(length)));
135 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
140 value = string.Empty;
142 if (startIndex > value.Length - length)
144 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_IndexLength);
147 m_MaxCapacity = int.MaxValue;
150 capacity = DefaultCapacity;
152 capacity = Math.Max(capacity, length);
154 m_ChunkChars = new char[capacity];
155 m_ChunkLength = length;
159 fixed (char* sourcePtr = value)
161 ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length);
167 /// Initializes a new instance of the <see cref="StringBuilder"/> class.
169 /// <param name="capacity">The initial capacity of this builder.</param>
170 /// <param name="maxCapacity">The maximum capacity of this builder.</param>
171 public StringBuilder(int capacity, int maxCapacity)
173 if (capacity > maxCapacity)
175 throw new ArgumentOutOfRangeException(nameof(capacity), SR.ArgumentOutOfRange_Capacity);
179 throw new ArgumentOutOfRangeException(nameof(maxCapacity), SR.ArgumentOutOfRange_SmallMaxCapacity);
183 throw new ArgumentOutOfRangeException(nameof(capacity), SR.Format(SR.ArgumentOutOfRange_MustBePositive, nameof(capacity)));
188 capacity = Math.Min(DefaultCapacity, maxCapacity);
191 m_MaxCapacity = maxCapacity;
192 m_ChunkChars = new char[capacity];
195 private StringBuilder(SerializationInfo info, StreamingContext context)
199 throw new ArgumentNullException(nameof(info));
202 int persistedCapacity = 0;
203 string persistedString = null;
204 int persistedMaxCapacity = Int32.MaxValue;
205 bool capacityPresent = false;
208 SerializationInfoEnumerator enumerator = info.GetEnumerator();
209 while (enumerator.MoveNext())
211 switch (enumerator.Name)
213 case MaxCapacityField:
214 persistedMaxCapacity = info.GetInt32(MaxCapacityField);
216 case StringValueField:
217 persistedString = info.GetString(StringValueField);
220 persistedCapacity = info.GetInt32(CapacityField);
221 capacityPresent = true;
224 // Ignore other fields for forwards-compatibility.
229 // Check values and set defaults
230 if (persistedString == null)
232 persistedString = string.Empty;
234 if (persistedMaxCapacity < 1 || persistedString.Length > persistedMaxCapacity)
236 throw new SerializationException(SR.Serialization_StringBuilderMaxCapacity);
239 if (!capacityPresent)
241 // StringBuilder in V1.X did not persist the Capacity, so this is a valid legacy code path.
242 persistedCapacity = Math.Min(Math.Max(DefaultCapacity, persistedString.Length), persistedMaxCapacity);
245 if (persistedCapacity < 0 || persistedCapacity < persistedString.Length || persistedCapacity > persistedMaxCapacity)
247 throw new SerializationException(SR.Serialization_StringBuilderCapacity);
251 m_MaxCapacity = persistedMaxCapacity;
252 m_ChunkChars = new char[persistedCapacity];
253 persistedString.CopyTo(0, m_ChunkChars, 0, persistedString.Length);
254 m_ChunkLength = persistedString.Length;
255 m_ChunkPrevious = null;
259 void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
263 throw new ArgumentNullException(nameof(info));
267 info.AddValue(MaxCapacityField, m_MaxCapacity);
268 info.AddValue(CapacityField, Capacity);
269 info.AddValue(StringValueField, ToString());
270 // Note: persist "m_currentThread" to be compatible with old versions
271 info.AddValue(ThreadIDField, 0);
274 [System.Diagnostics.Conditional("DEBUG")]
275 private void AssertInvariants()
277 Debug.Assert(m_ChunkOffset + m_ChunkChars.Length >= m_ChunkOffset, "The length of the string is greater than int.MaxValue.");
279 StringBuilder currentBlock = this;
280 int maxCapacity = this.m_MaxCapacity;
283 // All blocks have the same max capacity.
284 Debug.Assert(currentBlock.m_MaxCapacity == maxCapacity);
285 Debug.Assert(currentBlock.m_ChunkChars != null);
287 Debug.Assert(currentBlock.m_ChunkLength <= currentBlock.m_ChunkChars.Length);
288 Debug.Assert(currentBlock.m_ChunkLength >= 0);
289 Debug.Assert(currentBlock.m_ChunkOffset >= 0);
291 StringBuilder prevBlock = currentBlock.m_ChunkPrevious;
292 if (prevBlock == null)
294 Debug.Assert(currentBlock.m_ChunkOffset == 0);
297 // There are no gaps in the blocks.
298 Debug.Assert(currentBlock.m_ChunkOffset == prevBlock.m_ChunkOffset + prevBlock.m_ChunkLength);
299 currentBlock = prevBlock;
305 get { return m_ChunkChars.Length + m_ChunkOffset; }
310 throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_NegativeCapacity);
312 if (value > MaxCapacity)
314 throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_Capacity);
318 throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_SmallCapacity);
321 if (Capacity != value)
323 int newLen = value - m_ChunkOffset;
324 char[] newArray = new char[newLen];
325 Array.Copy(m_ChunkChars, 0, newArray, 0, m_ChunkLength);
326 m_ChunkChars = newArray;
332 /// Gets the maximum capacity this builder is allowed to have.
334 public int MaxCapacity => m_MaxCapacity;
337 /// Ensures that the capacity of this builder is at least the specified value.
339 /// <param name="capacity">The new capacity for this builder.</param>
341 /// If <paramref name="capacity"/> is less than or equal to the current capacity of
342 /// this builder, the capacity remains unchanged.
344 public int EnsureCapacity(int capacity)
348 throw new ArgumentOutOfRangeException(nameof(capacity), SR.ArgumentOutOfRange_NegativeCapacity);
351 if (Capacity < capacity)
356 public override String ToString()
365 string result = string.FastAllocateString(Length);
366 StringBuilder chunk = this;
369 fixed (char* destinationPtr = result)
373 if (chunk.m_ChunkLength > 0)
375 // Copy these into local variables so that they are stable even in the presence of race conditions
376 char[] sourceArray = chunk.m_ChunkChars;
377 int chunkOffset = chunk.m_ChunkOffset;
378 int chunkLength = chunk.m_ChunkLength;
380 // Check that we will not overrun our boundaries.
381 if ((uint)(chunkLength + chunkOffset) <= (uint)result.Length && (uint)chunkLength <= (uint)sourceArray.Length)
383 fixed (char* sourcePtr = &sourceArray[0])
384 string.wstrcpy(destinationPtr + chunkOffset, sourcePtr, chunkLength);
388 throw new ArgumentOutOfRangeException(nameof(chunkLength), SR.ArgumentOutOfRange_Index);
391 chunk = chunk.m_ChunkPrevious;
393 while (chunk != null);
401 /// Creates a string from a substring of this builder.
403 /// <param name="startIndex">The index to start in this builder.</param>
404 /// <param name="length">The number of characters to read in this builder.</param>
405 public string ToString(int startIndex, int length)
407 int currentLength = this.Length;
410 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
412 if (startIndex > currentLength)
414 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndexLargerThanLength);
418 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_NegativeLength);
420 if (startIndex > currentLength - length)
422 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_IndexLength);
426 string result = string.FastAllocateString(length);
429 fixed (char* destinationPtr = result)
431 this.CopyTo(startIndex, new Span<char>(destinationPtr, length), length);
437 public StringBuilder Clear()
444 /// Gets or sets the length of this builder.
450 return m_ChunkOffset + m_ChunkLength;
454 //If the new length is less than 0 or greater than our Maximum capacity, bail.
457 throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_NegativeLength);
460 if (value > MaxCapacity)
462 throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_SmallCapacity);
465 int originalCapacity = Capacity;
467 if (value == 0 && m_ChunkPrevious == null)
471 Debug.Assert(Capacity >= originalCapacity);
475 int delta = value - Length;
478 // Pad ourselves with null characters.
483 StringBuilder chunk = FindChunkForIndex(value);
486 // We crossed a chunk boundary when reducing the Length. We must replace this middle-chunk with a new larger chunk,
487 // to ensure the original capacity is preserved.
488 int newLen = originalCapacity - chunk.m_ChunkOffset;
489 char[] newArray = new char[newLen];
491 Debug.Assert(newLen > chunk.m_ChunkChars.Length, "The new chunk should be larger than the one it is replacing.");
492 Array.Copy(chunk.m_ChunkChars, 0, newArray, 0, chunk.m_ChunkLength);
494 m_ChunkChars = newArray;
495 m_ChunkPrevious = chunk.m_ChunkPrevious;
496 m_ChunkOffset = chunk.m_ChunkOffset;
498 m_ChunkLength = value - chunk.m_ChunkOffset;
501 Debug.Assert(Capacity >= originalCapacity);
505 [IndexerName("Chars")]
506 public char this[int index]
510 StringBuilder chunk = this;
513 int indexInBlock = index - chunk.m_ChunkOffset;
514 if (indexInBlock >= 0)
516 if (indexInBlock >= chunk.m_ChunkLength)
518 throw new IndexOutOfRangeException();
520 return chunk.m_ChunkChars[indexInBlock];
522 chunk = chunk.m_ChunkPrevious;
525 throw new IndexOutOfRangeException();
531 StringBuilder chunk = this;
534 int indexInBlock = index - chunk.m_ChunkOffset;
535 if (indexInBlock >= 0)
537 if (indexInBlock >= chunk.m_ChunkLength)
539 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
541 chunk.m_ChunkChars[indexInBlock] = value;
544 chunk = chunk.m_ChunkPrevious;
547 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
554 /// Appends a character 0 or more times to the end of this builder.
556 /// <param name="value">The character to append.</param>
557 /// <param name="repeatCount">The number of times to append <paramref name="value"/>.</param>
558 public StringBuilder Append(char value, int repeatCount)
562 throw new ArgumentOutOfRangeException(nameof(repeatCount), SR.ArgumentOutOfRange_NegativeCount);
565 if (repeatCount == 0)
570 // this is where we can check if the repeatCount will put us over m_MaxCapacity
571 // We are doing the check here to prevent the corruption of the StringBuilder.
572 int newLength = Length + repeatCount;
573 if (newLength > m_MaxCapacity || newLength < repeatCount)
575 throw new ArgumentOutOfRangeException(nameof(repeatCount), SR.ArgumentOutOfRange_LengthGreaterThanCapacity);
578 int index = m_ChunkLength;
579 while (repeatCount > 0)
581 if (index < m_ChunkChars.Length)
583 m_ChunkChars[index++] = value;
588 m_ChunkLength = index;
589 ExpandByABlock(repeatCount);
590 Debug.Assert(m_ChunkLength == 0);
595 m_ChunkLength = index;
601 /// Appends a range of characters to the end of this builder.
603 /// <param name="value">The characters to append.</param>
604 /// <param name="startIndex">The index to start in <paramref name="value"/>.</param>
605 /// <param name="charCount">The number of characters to read in <paramref name="value"/>.</param>
606 public StringBuilder Append(char[] value, int startIndex, int charCount)
610 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_GenericPositive);
614 throw new ArgumentOutOfRangeException(nameof(charCount), SR.ArgumentOutOfRange_GenericPositive);
619 if (startIndex == 0 && charCount == 0)
624 throw new ArgumentNullException(nameof(value));
626 if (charCount > value.Length - startIndex)
628 throw new ArgumentOutOfRangeException(nameof(charCount), SR.ArgumentOutOfRange_Index);
638 fixed (char* valueChars = &value[startIndex])
640 Append(valueChars, charCount);
648 /// Appends a string to the end of this builder.
650 /// <param name="value">The string to append.</param>
651 public StringBuilder Append(String value)
655 // We could have just called AppendHelper here; this is a hand-specialization of that code.
656 char[] chunkChars = m_ChunkChars;
657 int chunkLength = m_ChunkLength;
658 int valueLen = value.Length;
659 int newCurrentIndex = chunkLength + valueLen;
661 if (newCurrentIndex < chunkChars.Length) // Use strictly < to avoid issues if count == 0, newIndex == length
666 chunkChars[chunkLength] = value[0];
668 chunkChars[chunkLength + 1] = value[1];
674 fixed (char* valuePtr = value)
675 fixed (char* destPtr = &chunkChars[chunkLength])
677 string.wstrcpy(destPtr, valuePtr, valueLen);
682 m_ChunkLength = newCurrentIndex;
693 // We put this fixed in its own helper to avoid the cost of zero-initing `valueChars` in the
694 // case we don't actually use it.
695 private void AppendHelper(string value)
699 fixed (char* valueChars = value)
701 Append(valueChars, value.Length);
707 /// Appends part of a string to the end of this builder.
709 /// <param name="value">The string to append.</param>
710 /// <param name="startIndex">The index to start in <paramref name="value"/>.</param>
711 /// <param name="count">The number of characters to read in <paramref name="value"/>.</param>
712 public StringBuilder Append(string value, int startIndex, int count)
716 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
720 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_GenericPositive);
725 if (startIndex == 0 && count == 0)
729 throw new ArgumentNullException(nameof(value));
737 if (startIndex > value.Length - count)
739 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
744 fixed (char* valueChars = value)
746 Append(valueChars + startIndex, count);
752 public StringBuilder Append(StringBuilder value)
754 if (value != null && value.Length != 0)
756 return AppendCore(value, 0, value.Length);
761 public StringBuilder Append(StringBuilder value, int startIndex, int count)
765 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
770 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_GenericPositive);
775 if (startIndex == 0 && count == 0)
779 throw new ArgumentNullException(nameof(value));
787 if (count > value.Length - startIndex)
789 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
792 return AppendCore(value, startIndex, count);
795 private StringBuilder AppendCore(StringBuilder value, int startIndex, int count)
798 return Append(value.ToString(startIndex, count));
800 int newLength = Length + count;
802 if ((uint)newLength > (uint)m_MaxCapacity)
804 throw new ArgumentOutOfRangeException(nameof(Capacity), SR.ArgumentOutOfRange_Capacity);
809 int length = Math.Min(m_ChunkChars.Length - m_ChunkLength, count);
812 ExpandByABlock(count);
813 length = Math.Min(m_ChunkChars.Length - m_ChunkLength, count);
815 value.CopyTo(startIndex, new Span<char>(m_ChunkChars, m_ChunkLength, length), length);
817 m_ChunkLength += length;
818 startIndex += length;
825 public StringBuilder AppendLine() => Append(Environment.NewLine);
827 public StringBuilder AppendLine(string value)
830 return Append(Environment.NewLine);
833 public void CopyTo(int sourceIndex, char[] destination, int destinationIndex, int count)
835 if (destination == null)
837 throw new ArgumentNullException(nameof(destination));
840 if (destinationIndex < 0)
842 throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.Format(SR.ArgumentOutOfRange_MustBeNonNegNum, nameof(destinationIndex)));
845 if (destinationIndex > destination.Length - count)
847 throw new ArgumentException(SR.ArgumentOutOfRange_OffsetOut);
850 CopyTo(sourceIndex, new Span<char>(destination).Slice(destinationIndex), count);
853 public void CopyTo(int sourceIndex, Span<char> destination, int count)
857 throw new ArgumentOutOfRangeException(nameof(count), SR.Arg_NegativeArgCount);
860 if ((uint)sourceIndex > (uint)Length)
862 throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_Index);
865 if (sourceIndex > Length - count)
867 throw new ArgumentException(SR.Arg_LongerThanSrcString);
872 StringBuilder chunk = this;
873 int sourceEndIndex = sourceIndex + count;
874 int curDestIndex = count;
877 int chunkEndIndex = sourceEndIndex - chunk.m_ChunkOffset;
878 if (chunkEndIndex >= 0)
880 chunkEndIndex = Math.Min(chunkEndIndex, chunk.m_ChunkLength);
882 int chunkCount = count;
883 int chunkStartIndex = chunkEndIndex - count;
884 if (chunkStartIndex < 0)
886 chunkCount += chunkStartIndex;
889 curDestIndex -= chunkCount;
892 // We ensure that chunkStartIndex + chunkCount are within range of m_chunkChars as well as
893 // ensuring that curDestIndex + chunkCount are within range of destination
894 ThreadSafeCopy(chunk.m_ChunkChars, chunkStartIndex, destination, curDestIndex, chunkCount);
896 chunk = chunk.m_ChunkPrevious;
901 /// Inserts a string 0 or more times into this builder at the specified position.
903 /// <param name="index">The index to insert in this builder.</param>
904 /// <param name="value">The string to insert.</param>
905 /// <param name="count">The number of times to insert the string.</param>
906 public StringBuilder Insert(int index, String value, int count)
910 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NeedNonNegNum);
913 int currentLength = Length;
914 if ((uint)index > (uint)currentLength)
916 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
919 if (string.IsNullOrEmpty(value) || count == 0)
924 // Ensure we don't insert more chars than we can hold, and we don't
925 // have any integer overflow in our new length.
926 long insertingChars = (long)value.Length * count;
927 if (insertingChars > MaxCapacity - this.Length)
929 throw new OutOfMemoryException();
931 Debug.Assert(insertingChars + this.Length < int.MaxValue);
935 MakeRoom(index, (int)insertingChars, out chunk, out indexInChunk, false);
938 fixed (char* valuePtr = value)
942 ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, valuePtr, value.Length);
952 /// Removes a range of characters from this builder.
955 /// This method does not reduce the capacity of this builder.
957 public StringBuilder Remove(int startIndex, int length)
961 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_NegativeLength);
966 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
969 if (length > Length - startIndex)
971 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_Index);
974 if (Length == length && startIndex == 0)
984 Remove(startIndex, length, out chunk, out indexInChunk);
990 public StringBuilder Append(bool value) => Append(value.ToString());
992 public StringBuilder Append(char value)
994 if (m_ChunkLength < m_ChunkChars.Length)
996 m_ChunkChars[m_ChunkLength++] = value;
1006 [CLSCompliant(false)]
1007 public StringBuilder Append(sbyte value) => AppendSpanFormattable(value);
1009 public StringBuilder Append(byte value) => AppendSpanFormattable(value);
1011 public StringBuilder Append(short value) => AppendSpanFormattable(value);
1013 public StringBuilder Append(int value) => AppendSpanFormattable(value);
1015 public StringBuilder Append(long value) => AppendSpanFormattable(value);
1017 public StringBuilder Append(float value) => AppendSpanFormattable(value);
1019 public StringBuilder Append(double value) => AppendSpanFormattable(value);
1021 public StringBuilder Append(decimal value) => AppendSpanFormattable(value);
1023 [CLSCompliant(false)]
1024 public StringBuilder Append(ushort value) => AppendSpanFormattable(value);
1026 [CLSCompliant(false)]
1027 public StringBuilder Append(uint value) => AppendSpanFormattable(value);
1029 [CLSCompliant(false)]
1030 public StringBuilder Append(ulong value) => AppendSpanFormattable(value);
1032 private StringBuilder AppendSpanFormattable<T>(T value) where T : ISpanFormattable
1034 if (value.TryFormat(RemainingCurrentChunk, out int charsWritten, format: default, provider: null))
1036 m_ChunkLength += charsWritten;
1040 return Append(value.ToString());
1043 public StringBuilder Append(object value) => (value == null) ? this : Append(value.ToString());
1045 public StringBuilder Append(char[] value)
1047 if (value?.Length > 0)
1051 fixed (char* valueChars = &value[0])
1053 Append(valueChars, value.Length);
1060 public StringBuilder Append(ReadOnlySpan<char> value)
1062 if (value.Length > 0)
1066 fixed (char* valueChars = &MemoryMarshal.GetReference(value))
1068 Append(valueChars, value.Length);
1077 public unsafe StringBuilder AppendJoin(string separator, params object[] values)
1079 separator = separator ?? string.Empty;
1080 fixed (char* pSeparator = separator)
1082 return AppendJoinCore(pSeparator, separator.Length, values);
1086 public unsafe StringBuilder AppendJoin<T>(string separator, IEnumerable<T> values)
1088 separator = separator ?? string.Empty;
1089 fixed (char* pSeparator = separator)
1091 return AppendJoinCore(pSeparator, separator.Length, values);
1095 public unsafe StringBuilder AppendJoin(string separator, params string[] values)
1097 separator = separator ?? string.Empty;
1098 fixed (char* pSeparator = separator)
1100 return AppendJoinCore(pSeparator, separator.Length, values);
1104 public unsafe StringBuilder AppendJoin(char separator, params object[] values)
1106 return AppendJoinCore(&separator, 1, values);
1109 public unsafe StringBuilder AppendJoin<T>(char separator, IEnumerable<T> values)
1111 return AppendJoinCore(&separator, 1, values);
1114 public unsafe StringBuilder AppendJoin(char separator, params string[] values)
1116 return AppendJoinCore(&separator, 1, values);
1119 private unsafe StringBuilder AppendJoinCore<T>(char* separator, int separatorLength, IEnumerable<T> values)
1121 Debug.Assert(separator != null);
1122 Debug.Assert(separatorLength >= 0);
1126 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.values);
1129 using (IEnumerator<T> en = values.GetEnumerator())
1136 var value = en.Current;
1139 Append(value.ToString());
1142 while (en.MoveNext())
1144 Append(separator, separatorLength);
1148 Append(value.ToString());
1155 private unsafe StringBuilder AppendJoinCore<T>(char* separator, int separatorLength, T[] values)
1159 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.values);
1162 if (values.Length == 0)
1167 if (values[0] != null)
1169 Append(values[0].ToString());
1172 for (int i = 1; i < values.Length; i++)
1174 Append(separator, separatorLength);
1175 if (values[i] != null)
1177 Append(values[i].ToString());
1185 public StringBuilder Insert(int index, String value)
1187 if ((uint)index > (uint)Length)
1189 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
1196 fixed (char* sourcePtr = value)
1197 Insert(index, sourcePtr, value.Length);
1203 public StringBuilder Insert(int index, bool value) => Insert(index, value.ToString(), 1);
1205 [CLSCompliant(false)]
1206 public StringBuilder Insert(int index, sbyte value) => Insert(index, value.ToString(), 1);
1208 public StringBuilder Insert(int index, byte value) => Insert(index, value.ToString(), 1);
1210 public StringBuilder Insert(int index, short value) => Insert(index, value.ToString(), 1);
1212 public StringBuilder Insert(int index, char value)
1216 Insert(index, &value, 1);
1221 public StringBuilder Insert(int index, char[] value)
1223 if ((uint)index > (uint)Length)
1225 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
1229 Insert(index, value, 0, value.Length);
1233 public StringBuilder Insert(int index, char[] value, int startIndex, int charCount)
1235 int currentLength = Length;
1236 if ((uint)index > (uint)currentLength)
1238 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
1243 if (startIndex == 0 && charCount == 0)
1247 throw new ArgumentNullException(nameof(value), SR.ArgumentNull_String);
1252 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
1257 throw new ArgumentOutOfRangeException(nameof(charCount), SR.ArgumentOutOfRange_GenericPositive);
1260 if (startIndex > value.Length - charCount)
1262 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1269 fixed (char* sourcePtr = &value[startIndex])
1270 Insert(index, sourcePtr, charCount);
1276 public StringBuilder Insert(int index, int value) => Insert(index, value.ToString(), 1);
1278 public StringBuilder Insert(int index, long value) => Insert(index, value.ToString(), 1);
1280 public StringBuilder Insert(int index, float value) => Insert(index, value.ToString(), 1);
1282 public StringBuilder Insert(int index, double value) => Insert(index, value.ToString(), 1);
1284 public StringBuilder Insert(int index, decimal value) => Insert(index, value.ToString(), 1);
1286 [CLSCompliant(false)]
1287 public StringBuilder Insert(int index, ushort value) => Insert(index, value.ToString(), 1);
1289 [CLSCompliant(false)]
1290 public StringBuilder Insert(int index, uint value) => Insert(index, value.ToString(), 1);
1292 [CLSCompliant(false)]
1293 public StringBuilder Insert(int index, ulong value) => Insert(index, value.ToString(), 1);
1295 public StringBuilder Insert(int index, Object value) => (value == null) ? this : Insert(index, value.ToString(), 1);
1297 public StringBuilder Insert(int index, ReadOnlySpan<char> value)
1299 if ((uint)index > (uint)Length)
1301 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
1304 if (value.Length > 0)
1308 fixed (char* sourcePtr = &MemoryMarshal.GetReference(value))
1309 Insert(index, sourcePtr, value.Length);
1315 public StringBuilder AppendFormat(String format, Object arg0) => AppendFormatHelper(null, format, new ParamsArray(arg0));
1317 public StringBuilder AppendFormat(String format, Object arg0, Object arg1) => AppendFormatHelper(null, format, new ParamsArray(arg0, arg1));
1319 public StringBuilder AppendFormat(String format, Object arg0, Object arg1, Object arg2) => AppendFormatHelper(null, format, new ParamsArray(arg0, arg1, arg2));
1321 public StringBuilder AppendFormat(String format, params Object[] args)
1325 // To preserve the original exception behavior, throw an exception about format if both
1326 // args and format are null. The actual null check for format is in AppendFormatHelper.
1327 string paramName = (format == null) ? nameof(format) : nameof(args);
1328 throw new ArgumentNullException(paramName);
1331 return AppendFormatHelper(null, format, new ParamsArray(args));
1334 public StringBuilder AppendFormat(IFormatProvider provider, String format, Object arg0) => AppendFormatHelper(provider, format, new ParamsArray(arg0));
1336 public StringBuilder AppendFormat(IFormatProvider provider, String format, Object arg0, Object arg1) => AppendFormatHelper(provider, format, new ParamsArray(arg0, arg1));
1338 public StringBuilder AppendFormat(IFormatProvider provider, String format, Object arg0, Object arg1, Object arg2) => AppendFormatHelper(provider, format, new ParamsArray(arg0, arg1, arg2));
1340 public StringBuilder AppendFormat(IFormatProvider provider, String format, params Object[] args)
1344 // To preserve the original exception behavior, throw an exception about format if both
1345 // args and format are null. The actual null check for format is in AppendFormatHelper.
1346 string paramName = (format == null) ? nameof(format) : nameof(args);
1347 throw new ArgumentNullException(paramName);
1350 return AppendFormatHelper(provider, format, new ParamsArray(args));
1353 private static void FormatError()
1355 throw new FormatException(SR.Format_InvalidString);
1358 // Undocumented exclusive limits on the range for Argument Hole Index and Argument Hole Alignment.
1359 private const int IndexLimit = 1000000; // Note: 0 <= ArgIndex < IndexLimit
1360 private const int WidthLimit = 1000000; // Note: -WidthLimit < ArgAlign < WidthLimit
1362 internal StringBuilder AppendFormatHelper(IFormatProvider provider, String format, ParamsArray args)
1366 throw new ArgumentNullException(nameof(format));
1370 int len = format.Length;
1372 StringBuilder unescapedItemFormat = null;
1374 ICustomFormatter cf = null;
1375 if (provider != null)
1377 cf = (ICustomFormatter)provider.GetFormat(typeof(ICustomFormatter));
1387 // Is it a closing brace?
1390 // Check next character (if there is one) to see if it is escaped. eg }}
1391 if (pos < len && format[pos] == '}')
1394 // Otherwise treat it as an error (Mismatched closing brace)
1397 // Is it a opening brace?
1400 // Check next character (if there is one) to see if it is escaped. eg {{
1401 if (pos < len && format[pos] == '{')
1405 // Otherwise treat it as the opening brace of an Argument Hole.
1410 // If it neither then treat the character as just text.
1415 // Start of parsing of Argument Hole.
1416 // Argument Hole ::= { Index (, WS* Alignment WS*)? (: Formatting)? }
1418 if (pos == len) break;
1421 // Start of parsing required Index parameter.
1422 // Index ::= ('0'-'9')+ WS*
1425 // If reached end of text then error (Unexpected end of text)
1426 // or character is not a digit then error (Unexpected Character)
1427 if (pos == len || (ch = format[pos]) < '0' || ch > '9') FormatError();
1431 index = index * 10 + ch - '0';
1433 // If reached end of text then error (Unexpected end of text)
1434 if (pos == len) FormatError();
1436 // so long as character is digit and value of the index is less than 1000000 ( index limit )
1438 while (ch >= '0' && ch <= '9' && index < IndexLimit);
1440 // If value of index is not within the range of the arguments passed in then error (Index out of range)
1441 if (index >= args.Length) throw new FormatException(SR.Format_IndexOutOfRange);
1443 // Consume optional whitespace.
1444 while (pos < len && (ch = format[pos]) == ' ') pos++;
1445 // End of parsing index parameter.
1448 // Start of parsing of optional Alignment
1449 // Alignment ::= comma WS* minus? ('0'-'9')+ WS*
1451 bool leftJustify = false;
1453 // Is the character a comma, which indicates the start of alignment parameter.
1458 // Consume Optional whitespace
1459 while (pos < len && format[pos] == ' ') pos++;
1461 // If reached the end of the text then error (Unexpected end of text)
1462 if (pos == len) FormatError();
1464 // Is there a minus sign?
1468 // Yes, then alignment is left justified.
1471 // If reached end of text then error (Unexpected end of text)
1472 if (pos == len) FormatError();
1476 // If current character is not a digit then error (Unexpected character)
1477 if (ch < '0' || ch > '9') FormatError();
1478 // Parse alignment digits.
1481 width = width * 10 + ch - '0';
1483 // If reached end of text then error. (Unexpected end of text)
1484 if (pos == len) FormatError();
1486 // So long a current character is a digit and the value of width is less than 100000 ( width limit )
1488 while (ch >= '0' && ch <= '9' && width < WidthLimit);
1489 // end of parsing Argument Alignment
1492 // Consume optional whitespace
1493 while (pos < len && (ch = format[pos]) == ' ') pos++;
1496 // Start of parsing of optional formatting parameter.
1498 Object arg = args[index];
1499 String itemFormat = null;
1500 ReadOnlySpan<char> itemFormatSpan = default; // used if itemFormat is null
1501 // Is current character a colon? which indicates start of formatting parameter.
1509 // If reached end of text then error. (Unexpected end of text)
1510 if (pos == len) FormatError();
1514 // Is character a opening or closing brace?
1515 if (ch == '}' || ch == '{')
1519 // Yes, is next character also a opening brace, then treat as escaped. eg {{
1520 if (pos < len && format[pos] == '{')
1523 // Error Argument Holes can not be nested.
1528 // Yes, is next character also a closing brace, then treat as escaped. eg }}
1529 if (pos < len && format[pos] == '}')
1533 // No, then treat it as the closing brace of an Arg Hole.
1539 // Reaching here means the brace has been escaped
1540 // so we need to build up the format string in segments
1541 if (unescapedItemFormat == null)
1543 unescapedItemFormat = new StringBuilder();
1545 unescapedItemFormat.Append(format, startPos, pos - startPos - 1);
1550 if (unescapedItemFormat == null || unescapedItemFormat.Length == 0)
1552 if (startPos != pos)
1554 // There was no brace escaping, extract the item format as a single string
1555 itemFormatSpan = format.AsSpan(startPos, pos - startPos);
1560 unescapedItemFormat.Append(format, startPos, pos - startPos);
1561 itemFormatSpan = itemFormat = unescapedItemFormat.ToString();
1562 unescapedItemFormat.Clear();
1565 // If current character is not a closing brace then error. (Unexpected Character)
1566 if (ch != '}') FormatError();
1567 // Construct the output for this arg hole.
1572 if (itemFormatSpan.Length != 0 && itemFormat == null)
1574 itemFormat = new string(itemFormatSpan);
1576 s = cf.Format(itemFormat, arg, provider);
1581 // If arg is ISpanFormattable and the beginning doesn't need padding,
1582 // try formatting it into the remaining current chunk.
1583 if (arg is ISpanFormattable spanFormattableArg &&
1584 (leftJustify || width == 0) &&
1585 spanFormattableArg.TryFormat(RemainingCurrentChunk, out int charsWritten, itemFormatSpan, provider))
1587 m_ChunkLength += charsWritten;
1589 // Pad the end, if needed.
1590 int padding = width - charsWritten;
1591 if (leftJustify && padding > 0) Append(' ', padding);
1593 // Continue to parse other characters.
1597 // Otherwise, fallback to trying IFormattable or calling ToString.
1598 if (arg is IFormattable formattableArg)
1600 if (itemFormatSpan.Length != 0 && itemFormat == null)
1602 itemFormat = new string(itemFormatSpan);
1604 s = formattableArg.ToString(itemFormat, provider);
1606 else if (arg != null)
1611 // Append it to the final output of the Format String.
1612 if (s == null) s = String.Empty;
1613 int pad = width - s.Length;
1614 if (!leftJustify && pad > 0) Append(' ', pad);
1616 if (leftJustify && pad > 0) Append(' ', pad);
1617 // Continue to parse other characters.
1623 /// Replaces all instances of one string with another in this builder.
1625 /// <param name="oldValue">The string to replace.</param>
1626 /// <param name="newValue">The string to replace <paramref name="oldValue"/> with.</param>
1628 /// If <paramref name="newValue"/> is <c>null</c>, instances of <paramref name="oldValue"/>
1629 /// are removed from this builder.
1631 public StringBuilder Replace(String oldValue, String newValue) => Replace(oldValue, newValue, 0, Length);
1634 /// Determines if the contents of this builder are equal to the contents of another builder.
1636 /// <param name="sb">The other builder.</param>
1637 public bool Equals(StringBuilder sb)
1641 if (Capacity != sb.Capacity || MaxCapacity != sb.MaxCapacity || Length != sb.Length)
1646 StringBuilder thisChunk = this;
1647 int thisChunkIndex = thisChunk.m_ChunkLength;
1648 StringBuilder sbChunk = sb;
1649 int sbChunkIndex = sbChunk.m_ChunkLength;
1655 while (thisChunkIndex < 0)
1657 thisChunk = thisChunk.m_ChunkPrevious;
1658 if (thisChunk == null)
1660 thisChunkIndex = thisChunk.m_ChunkLength + thisChunkIndex;
1663 while (sbChunkIndex < 0)
1665 sbChunk = sbChunk.m_ChunkPrevious;
1666 if (sbChunk == null)
1668 sbChunkIndex = sbChunk.m_ChunkLength + sbChunkIndex;
1671 if (thisChunkIndex < 0)
1672 return sbChunkIndex < 0;
1673 if (sbChunkIndex < 0)
1675 if (thisChunk.m_ChunkChars[thisChunkIndex] != sbChunk.m_ChunkChars[sbChunkIndex])
1681 /// Determines if the contents of this builder are equal to the contents of ReadOnlySpan<char>.
1683 /// <param name="value">The ReadOnlySpan{char}.</param>
1684 public bool Equals(ReadOnlySpan<char> value)
1686 if (value.Length != Length)
1689 StringBuilder sbChunk = this;
1694 int chunk_length = sbChunk.m_ChunkLength;
1695 offset += chunk_length;
1697 ReadOnlySpan<char> chunk = new ReadOnlySpan<char>(sbChunk.m_ChunkChars, 0, chunk_length);
1699 if (!chunk.EqualsOrdinal(value.Slice(value.Length - offset, chunk_length)))
1702 sbChunk = sbChunk.m_ChunkPrevious;
1703 } while (sbChunk != null);
1705 Debug.Assert(offset == Length);
1710 /// Replaces all instances of one string with another in part of this builder.
1712 /// <param name="oldValue">The string to replace.</param>
1713 /// <param name="newValue">The string to replace <paramref name="oldValue"/> with.</param>
1714 /// <param name="startIndex">The index to start in this builder.</param>
1715 /// <param name="count">The number of characters to read in this builder.</param>
1717 /// If <paramref name="newValue"/> is <c>null</c>, instances of <paramref name="oldValue"/>
1718 /// are removed from this builder.
1720 public StringBuilder Replace(String oldValue, String newValue, int startIndex, int count)
1722 int currentLength = Length;
1723 if ((uint)startIndex > (uint)currentLength)
1725 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1727 if (count < 0 || startIndex > currentLength - count)
1729 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Index);
1731 if (oldValue == null)
1733 throw new ArgumentNullException(nameof(oldValue));
1735 if (oldValue.Length == 0)
1737 throw new ArgumentException(SR.Argument_EmptyName, nameof(oldValue));
1740 newValue = newValue ?? string.Empty;
1742 int deltaLength = newValue.Length - oldValue.Length;
1744 int[] replacements = null; // A list of replacement positions in a chunk to apply
1745 int replacementsCount = 0;
1747 // Find the chunk, indexInChunk for the starting point
1748 StringBuilder chunk = FindChunkForIndex(startIndex);
1749 int indexInChunk = startIndex - chunk.m_ChunkOffset;
1752 // Look for a match in the chunk,indexInChunk pointer
1753 if (StartsWith(chunk, indexInChunk, count, oldValue))
1755 // Push it on the replacements array (with growth), we will do all replacements in a
1756 // given chunk in one operation below (see ReplaceAllInChunk) so we don't have to slide
1758 if (replacements == null)
1760 replacements = new int[5];
1762 else if (replacementsCount >= replacements.Length)
1764 Array.Resize(ref replacements, replacements.Length * 3 / 2 + 4); // Grow by ~1.5x, but more in the begining
1766 replacements[replacementsCount++] = indexInChunk;
1767 indexInChunk += oldValue.Length;
1768 count -= oldValue.Length;
1776 if (indexInChunk >= chunk.m_ChunkLength || count == 0) // Have we moved out of the current chunk?
1778 // Replacing mutates the blocks, so we need to convert to a logical index and back afterwards.
1779 int index = indexInChunk + chunk.m_ChunkOffset;
1780 int indexBeforeAdjustment = index;
1782 // See if we accumulated any replacements, if so apply them.
1783 ReplaceAllInChunk(replacements, replacementsCount, chunk, oldValue.Length, newValue);
1784 // The replacement has affected the logical index. Adjust it.
1785 index += ((newValue.Length - oldValue.Length) * replacementsCount);
1786 replacementsCount = 0;
1788 chunk = FindChunkForIndex(index);
1789 indexInChunk = index - chunk.m_ChunkOffset;
1790 Debug.Assert(chunk != null || count == 0, "Chunks ended prematurely!");
1799 /// Replaces all instances of one character with another in this builder.
1801 /// <param name="oldChar">The character to replace.</param>
1802 /// <param name="newChar">The character to replace <paramref name="oldChar"/> with.</param>
1803 public StringBuilder Replace(char oldChar, char newChar)
1805 return Replace(oldChar, newChar, 0, Length);
1809 /// Replaces all instances of one character with another in this builder.
1811 /// <param name="oldChar">The character to replace.</param>
1812 /// <param name="newChar">The character to replace <paramref name="oldChar"/> with.</param>
1813 /// <param name="startIndex">The index to start in this builder.</param>
1814 /// <param name="count">The number of characters to read in this builder.</param>
1815 public StringBuilder Replace(char oldChar, char newChar, int startIndex, int count)
1817 int currentLength = Length;
1818 if ((uint)startIndex > (uint)currentLength)
1820 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1823 if (count < 0 || startIndex > currentLength - count)
1825 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Index);
1828 int endIndex = startIndex + count;
1829 StringBuilder chunk = this;
1833 int endIndexInChunk = endIndex - chunk.m_ChunkOffset;
1834 int startIndexInChunk = startIndex - chunk.m_ChunkOffset;
1835 if (endIndexInChunk >= 0)
1837 int curInChunk = Math.Max(startIndexInChunk, 0);
1838 int endInChunk = Math.Min(chunk.m_ChunkLength, endIndexInChunk);
1839 while (curInChunk < endInChunk)
1841 if (chunk.m_ChunkChars[curInChunk] == oldChar)
1842 chunk.m_ChunkChars[curInChunk] = newChar;
1846 if (startIndexInChunk >= 0)
1848 chunk = chunk.m_ChunkPrevious;
1856 /// Appends a character buffer to this builder.
1858 /// <param name="value">The pointer to the start of the buffer.</param>
1859 /// <param name="valueCount">The number of characters in the buffer.</param>
1860 [CLSCompliant(false)]
1861 public unsafe StringBuilder Append(char* value, int valueCount)
1863 // We don't check null value as this case will throw null reference exception anyway
1866 throw new ArgumentOutOfRangeException(nameof(valueCount), SR.ArgumentOutOfRange_NegativeCount);
1869 // this is where we can check if the valueCount will put us over m_MaxCapacity
1870 // We are doing the check here to prevent the corruption of the StringBuilder.
1871 int newLength = Length + valueCount;
1872 if (newLength > m_MaxCapacity || newLength < valueCount)
1874 throw new ArgumentOutOfRangeException(nameof(valueCount), SR.ArgumentOutOfRange_LengthGreaterThanCapacity);
1877 // This case is so common we want to optimize for it heavily.
1878 int newIndex = valueCount + m_ChunkLength;
1879 if (newIndex <= m_ChunkChars.Length)
1881 ThreadSafeCopy(value, m_ChunkChars, m_ChunkLength, valueCount);
1882 m_ChunkLength = newIndex;
1886 // Copy the first chunk
1887 int firstLength = m_ChunkChars.Length - m_ChunkLength;
1888 if (firstLength > 0)
1890 ThreadSafeCopy(value, m_ChunkChars, m_ChunkLength, firstLength);
1891 m_ChunkLength = m_ChunkChars.Length;
1894 // Expand the builder to add another chunk.
1895 int restLength = valueCount - firstLength;
1896 ExpandByABlock(restLength);
1897 Debug.Assert(m_ChunkLength == 0, "A new block was not created.");
1899 // Copy the second chunk
1900 ThreadSafeCopy(value + firstLength, m_ChunkChars, 0, restLength);
1901 m_ChunkLength = restLength;
1908 /// Inserts a character buffer into this builder at the specified position.
1910 /// <param name="index">The index to insert in this builder.</param>
1911 /// <param name="value">The pointer to the start of the buffer.</param>
1912 /// <param name="valueCount">The number of characters in the buffer.</param>
1913 private unsafe void Insert(int index, char* value, int valueCount)
1915 if ((uint)index > (uint)Length)
1917 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
1922 StringBuilder chunk;
1924 MakeRoom(index, valueCount, out chunk, out indexInChunk, false);
1925 ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, value, valueCount);
1930 /// Replaces strings at specified indices with a new string in a chunk.
1932 /// <param name="replacements">The list of indices, relative to the beginning of the chunk, to remove at.</param>
1933 /// <param name="replacementsCount">The number of replacements to make.</param>
1934 /// <param name="sourceChunk">The source chunk.</param>
1935 /// <param name="removeCount">The number of characters to remove at each replacement.</param>
1936 /// <param name="value">The string to insert at each replacement.</param>
1938 /// This routine is very efficient because it does replacements in bulk.
1940 private void ReplaceAllInChunk(int[] replacements, int replacementsCount, StringBuilder sourceChunk, int removeCount, string value)
1942 if (replacementsCount <= 0)
1949 fixed (char* valuePtr = value)
1951 // calculate the total amount of extra space or space needed for all the replacements.
1952 int delta = (value.Length - removeCount) * replacementsCount;
1954 StringBuilder targetChunk = sourceChunk; // the target as we copy chars down
1955 int targetIndexInChunk = replacements[0];
1957 // Make the room needed for all the new characters if needed.
1959 MakeRoom(targetChunk.m_ChunkOffset + targetIndexInChunk, delta, out targetChunk, out targetIndexInChunk, true);
1960 // We made certain that characters after the insertion point are not moved,
1964 // Copy in the new string for the ith replacement
1965 ReplaceInPlaceAtChunk(ref targetChunk, ref targetIndexInChunk, valuePtr, value.Length);
1966 int gapStart = replacements[i] + removeCount;
1968 if (i >= replacementsCount)
1973 int gapEnd = replacements[i];
1974 Debug.Assert(gapStart < sourceChunk.m_ChunkChars.Length, "gap starts at end of buffer. Should not happen");
1975 Debug.Assert(gapStart <= gapEnd, "negative gap size");
1976 Debug.Assert(gapEnd <= sourceChunk.m_ChunkLength, "gap too big");
1977 if (delta != 0) // can skip the sliding of gaps if source an target string are the same size.
1979 // Copy the gap data between the current replacement and the next replacement
1980 fixed (char* sourcePtr = &sourceChunk.m_ChunkChars[gapStart])
1981 ReplaceInPlaceAtChunk(ref targetChunk, ref targetIndexInChunk, sourcePtr, gapEnd - gapStart);
1985 targetIndexInChunk += gapEnd - gapStart;
1986 Debug.Assert(targetIndexInChunk <= targetChunk.m_ChunkLength, "gap not in chunk");
1990 // Remove extra space if necessary.
1992 Remove(targetChunk.m_ChunkOffset + targetIndexInChunk, -delta, out targetChunk, out targetIndexInChunk);
1998 /// Returns a value indicating whether a substring of a builder starts with a specified prefix.
2000 /// <param name="chunk">The chunk in which the substring starts.</param>
2001 /// <param name="indexInChunk">The index in <paramref name="chunk"/> at which the substring starts.</param>
2002 /// <param name="count">The logical count of the substring.</param>
2003 /// <param name="value">The prefix.</param>
2004 private bool StartsWith(StringBuilder chunk, int indexInChunk, int count, string value)
2006 for (int i = 0; i < value.Length; i++)
2013 if (indexInChunk >= chunk.m_ChunkLength)
2015 chunk = Next(chunk);
2021 if (value[i] != chunk.m_ChunkChars[indexInChunk])
2034 /// Replaces characters at a specified location with the contents of a character buffer.
2035 /// This function is the logical equivalent of memcpy.
2037 /// <param name="chunk">
2038 /// The chunk in which to start replacing characters.
2039 /// Receives the chunk in which character replacement ends.
2041 /// <param name="indexInChunk">
2042 /// The index in <paramref name="chunk"/> to start replacing characters at.
2043 /// Receives the index at which character replacement ends.
2045 /// <param name="value">The pointer to the start of the character buffer.</param>
2046 /// <param name="count">The number of characters in the buffer.</param>
2047 private unsafe void ReplaceInPlaceAtChunk(ref StringBuilder chunk, ref int indexInChunk, char* value, int count)
2053 int lengthInChunk = chunk.m_ChunkLength - indexInChunk;
2054 Debug.Assert(lengthInChunk >= 0, "Index isn't in the chunk.");
2056 int lengthToCopy = Math.Min(lengthInChunk, count);
2057 ThreadSafeCopy(value, chunk.m_ChunkChars, indexInChunk, lengthToCopy);
2059 // Advance the index.
2060 indexInChunk += lengthToCopy;
2061 if (indexInChunk >= chunk.m_ChunkLength)
2063 chunk = Next(chunk);
2066 count -= lengthToCopy;
2071 value += lengthToCopy;
2077 /// This method prevents out-of-bounds writes in the case a different thread updates a field in the builder just before a copy begins.
2078 /// All interesting variables are copied out of the heap into the parameters of this method, and then bounds checks are run.
2080 private static unsafe void ThreadSafeCopy(char* sourcePtr, char[] destination, int destinationIndex, int count)
2084 if ((uint)destinationIndex <= (uint)destination.Length && (destinationIndex + count) <= destination.Length)
2086 fixed (char* destinationPtr = &destination[destinationIndex])
2087 string.wstrcpy(destinationPtr, sourcePtr, count);
2091 throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.ArgumentOutOfRange_Index);
2096 private static unsafe void ThreadSafeCopy(char[] source, int sourceIndex, Span<char> destination, int destinationIndex, int count)
2100 if ((uint)sourceIndex > (uint)source.Length || count > source.Length - sourceIndex)
2102 throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_Index);
2105 if ((uint)destinationIndex > (uint)destination.Length || count > destination.Length - destinationIndex)
2107 throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.ArgumentOutOfRange_Index);
2110 fixed (char* sourcePtr = &source[sourceIndex])
2111 fixed (char* destinationPtr = &MemoryMarshal.GetReference(destination))
2112 string.wstrcpy(destinationPtr + destinationIndex, sourcePtr, count);
2117 /// Gets the chunk corresponding to the logical index in this builder.
2119 /// <param name="index">The logical index in this builder.</param>
2121 /// After calling this method, you can obtain the actual index within the chunk by
2122 /// subtracting <see cref="m_ChunkOffset"/> from <paramref name="index"/>.
2124 private StringBuilder FindChunkForIndex(int index)
2126 Debug.Assert(0 <= index && index <= Length);
2128 StringBuilder result = this;
2129 while (result.m_ChunkOffset > index)
2131 result = result.m_ChunkPrevious;
2134 Debug.Assert(result != null);
2139 /// Gets the chunk corresponding to the logical byte index in this builder.
2141 /// <param name="byteIndex">The logical byte index in this builder.</param>
2142 private StringBuilder FindChunkForByte(int byteIndex)
2144 Debug.Assert(0 <= byteIndex && byteIndex <= Length * sizeof(char));
2146 StringBuilder result = this;
2147 while (result.m_ChunkOffset * sizeof(char) > byteIndex)
2149 result = result.m_ChunkPrevious;
2152 Debug.Assert(result != null);
2156 /// <summary>Gets a span representing the remaining space available in the current chunk.</summary>
2157 private Span<char> RemainingCurrentChunk
2159 [MethodImpl(MethodImplOptions.AggressiveInlining)]
2160 get => new Span<char>(m_ChunkChars, m_ChunkLength, m_ChunkChars.Length - m_ChunkLength);
2164 /// Finds the chunk that logically succeeds the specified chunk.
2166 /// <param name="chunk">The chunk whose successor should be found.</param>
2168 /// Each chunk only stores the pointer to its logical predecessor, so this routine has to start
2169 /// from the 'this' pointer (which is assumed to represent the whole StringBuilder) and work its
2170 /// way down until it finds the specified chunk (which is O(n)). Thus, it is more expensive than
2173 private StringBuilder Next(StringBuilder chunk) => chunk == this ? null : FindChunkForIndex(chunk.m_ChunkOffset + chunk.m_ChunkLength);
2176 /// Transfers the character buffer from this chunk to a new chunk, and allocates a new buffer with a minimum size for this chunk.
2178 /// <param name="minBlockCharCount">The minimum size of the new buffer to be allocated for this chunk.</param>
2180 /// This method requires that the current chunk is full. Otherwise, there's no point in shifting the characters over.
2181 /// It also assumes that 'this' is the last chunk in the linked list.
2183 private void ExpandByABlock(int minBlockCharCount)
2185 Debug.Assert(Capacity == Length, nameof(ExpandByABlock) + " should only be called when there is no space left.");
2186 Debug.Assert(minBlockCharCount > 0);
2190 if ((minBlockCharCount + Length) > m_MaxCapacity || minBlockCharCount + Length < minBlockCharCount)
2192 throw new ArgumentOutOfRangeException("requiredLength", SR.ArgumentOutOfRange_SmallCapacity);
2195 // - We always need to make the new chunk at least as big as was requested (`minBlockCharCount`).
2196 // - We'd also prefer to make it at least at big as the current length (thus doubling capacity).
2197 // - But this is only up to a maximum, so we stay in the small object heap, and never allocate
2198 // really big chunks even if the string gets really big.
2199 int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));
2201 // Move all of the data from this chunk to a new one, via a few O(1) pointer adjustments.
2202 // Then, have this chunk point to the new one as its predecessor.
2203 m_ChunkPrevious = new StringBuilder(this);
2204 m_ChunkOffset += m_ChunkLength;
2207 // Check for integer overflow (logical buffer size > int.MaxValue)
2208 if (m_ChunkOffset + newBlockLength < newBlockLength)
2210 m_ChunkChars = null;
2211 throw new OutOfMemoryException();
2213 m_ChunkChars = new char[newBlockLength];
2219 /// Creates a new chunk with fields copied from an existing chunk.
2221 /// <param name="from">The chunk from which to copy fields.</param>
2224 /// This method runs in O(1) time. It does not copy data within the character buffer
2225 /// <paramref name="from"/> holds, but copies the reference to the character buffer itself
2226 /// (plus a few other fields).
2229 /// Callers are expected to update <paramref name="from"/> subsequently to point to this
2230 /// chunk as its predecessor.
2233 private StringBuilder(StringBuilder from)
2235 m_ChunkLength = from.m_ChunkLength;
2236 m_ChunkOffset = from.m_ChunkOffset;
2237 m_ChunkChars = from.m_ChunkChars;
2238 m_ChunkPrevious = from.m_ChunkPrevious;
2239 m_MaxCapacity = from.m_MaxCapacity;
2245 /// Creates a gap at a logical index with the specified count.
2247 /// <param name="index">The logical index in this builder.</param>
2248 /// <param name="count">The number of characters in the gap.</param>
2249 /// <param name="chunk">Receives the chunk containing the gap.</param>
2250 /// <param name="indexInChunk">The index in <paramref name="chunk"/> that points to the gap.</param>
2251 /// <param name="doNotMoveFollowingChars">
2252 /// - If <c>true</c>, then room must be made by inserting a chunk before the current chunk.
2253 /// - If <c>false</c>, then room can be made by shifting characters ahead of <paramref name="index"/>
2254 /// in this block forward by <paramref name="count"/> provided the characters will still fit in
2255 /// the current chunk after being shifted.
2256 /// - Providing <c>false</c> does not make a difference most of the time, but it can matter when someone
2257 /// inserts lots of small strings at a position in the buffer.
2261 /// Since chunks do not contain references to their successors, it is not always possible for us to make room
2262 /// by inserting space after <paramref name="index"/> in case this chunk runs out of space. Thus, we make room
2263 /// by inserting space before the specified index, and having logical indices refer to new locations by the end
2267 /// <see cref="ReplaceInPlaceAtChunk"/> can be used in conjunction with this method to fill in the newly created gap.
2270 private void MakeRoom(int index, int count, out StringBuilder chunk, out int indexInChunk, bool doNotMoveFollowingChars)
2273 Debug.Assert(count > 0);
2274 Debug.Assert(index >= 0);
2276 if (count + Length > m_MaxCapacity || count + Length < count)
2278 throw new ArgumentOutOfRangeException("requiredLength", SR.ArgumentOutOfRange_SmallCapacity);
2282 while (chunk.m_ChunkOffset > index)
2284 chunk.m_ChunkOffset += count;
2285 chunk = chunk.m_ChunkPrevious;
2287 indexInChunk = index - chunk.m_ChunkOffset;
2289 // Cool, we have some space in this block, and we don't have to copy much to get at it, so go ahead and use it.
2290 // This typically happens when someone repeatedly inserts small strings at a spot (usually the absolute front) of the buffer.
2291 if (!doNotMoveFollowingChars && chunk.m_ChunkLength <= DefaultCapacity * 2 && chunk.m_ChunkChars.Length - chunk.m_ChunkLength >= count)
2293 for (int i = chunk.m_ChunkLength; i > indexInChunk; )
2296 chunk.m_ChunkChars[i + count] = chunk.m_ChunkChars[i];
2298 chunk.m_ChunkLength += count;
2302 // Allocate space for the new chunk, which will go before the current one.
2303 StringBuilder newChunk = new StringBuilder(Math.Max(count, DefaultCapacity), chunk.m_MaxCapacity, chunk.m_ChunkPrevious);
2304 newChunk.m_ChunkLength = count;
2306 // Copy the head of the current buffer to the new buffer.
2307 int copyCount1 = Math.Min(count, indexInChunk);
2312 fixed (char* chunkCharsPtr = &chunk.m_ChunkChars[0])
2314 ThreadSafeCopy(chunkCharsPtr, newChunk.m_ChunkChars, 0, copyCount1);
2316 // Slide characters over in the current buffer to make room.
2317 int copyCount2 = indexInChunk - copyCount1;
2318 if (copyCount2 >= 0)
2320 ThreadSafeCopy(chunkCharsPtr + copyCount1, chunk.m_ChunkChars, 0, copyCount2);
2321 indexInChunk = copyCount2;
2327 // Wire in the new chunk.
2328 chunk.m_ChunkPrevious = newChunk;
2329 chunk.m_ChunkOffset += count;
2330 if (copyCount1 < count)
2333 indexInChunk = copyCount1;
2340 /// Used by <see cref="MakeRoom"/> to allocate another chunk.
2342 /// <param name="size">The size of the character buffer for this chunk.</param>
2343 /// <param name="maxCapacity">The maximum capacity, to be stored in this chunk.</param>
2344 /// <param name="previousBlock">The predecessor of this chunk.</param>
2345 private StringBuilder(int size, int maxCapacity, StringBuilder previousBlock)
2347 Debug.Assert(size > 0);
2348 Debug.Assert(maxCapacity > 0);
2350 m_ChunkChars = new char[size];
2351 m_MaxCapacity = maxCapacity;
2352 m_ChunkPrevious = previousBlock;
2353 if (previousBlock != null)
2355 m_ChunkOffset = previousBlock.m_ChunkOffset + previousBlock.m_ChunkLength;
2362 /// Removes a specified number of characters beginning at a logical index in this builder.
2364 /// <param name="startIndex">The logical index in this builder to start removing characters.</param>
2365 /// <param name="count">The number of characters to remove.</param>
2366 /// <param name="chunk">Receives the new chunk containing the logical index.</param>
2367 /// <param name="indexInChunk">
2368 /// Receives the new index in <paramref name="chunk"/> that is associated with the logical index.
2370 private void Remove(int startIndex, int count, out StringBuilder chunk, out int indexInChunk)
2373 Debug.Assert(startIndex >= 0 && startIndex < Length);
2375 int endIndex = startIndex + count;
2377 // Find the chunks for the start and end of the block to delete.
2379 StringBuilder endChunk = null;
2380 int endIndexInChunk = 0;
2383 if (endIndex - chunk.m_ChunkOffset >= 0)
2385 if (endChunk == null)
2388 endIndexInChunk = endIndex - endChunk.m_ChunkOffset;
2390 if (startIndex - chunk.m_ChunkOffset >= 0)
2392 indexInChunk = startIndex - chunk.m_ChunkOffset;
2398 chunk.m_ChunkOffset -= count;
2400 chunk = chunk.m_ChunkPrevious;
2402 Debug.Assert(chunk != null, "We fell off the beginning of the string!");
2404 int copyTargetIndexInChunk = indexInChunk;
2405 int copyCount = endChunk.m_ChunkLength - endIndexInChunk;
2406 if (endChunk != chunk)
2408 copyTargetIndexInChunk = 0;
2409 // Remove the characters after `startIndex` to the end of the chunk.
2410 chunk.m_ChunkLength = indexInChunk;
2412 // Remove the characters in chunks between the start and the end chunk.
2413 endChunk.m_ChunkPrevious = chunk;
2414 endChunk.m_ChunkOffset = chunk.m_ChunkOffset + chunk.m_ChunkLength;
2416 // If the start is 0, then we can throw away the whole start chunk.
2417 if (indexInChunk == 0)
2419 endChunk.m_ChunkPrevious = chunk.m_ChunkPrevious;
2423 endChunk.m_ChunkLength -= (endIndexInChunk - copyTargetIndexInChunk);
2425 // SafeCritical: We ensure that `endIndexInChunk + copyCount` is within range of `m_ChunkChars`, and
2426 // also ensure that `copyTargetIndexInChunk + copyCount` is within the chunk.
2428 // Remove any characters in the end chunk, by sliding the characters down.
2429 if (copyTargetIndexInChunk != endIndexInChunk) // Sometimes no move is necessary
2431 ThreadSafeCopy(endChunk.m_ChunkChars, endIndexInChunk, endChunk.m_ChunkChars, copyTargetIndexInChunk, copyCount);
2434 Debug.Assert(chunk != null, "We fell off the beginning of the string!");