// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using System.Text;
using System.Runtime;
using System.Runtime.Serialization;
using System;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Versioning;
using System.Security;
using System.Threading;
using System.Globalization;
using System.Diagnostics;
using System.Collections.Generic;
namespace System.Text
{
// This class represents a mutable string. It is convenient for situations in
// which it is desirable to modify a string, perhaps by removing, replacing, or
// inserting characters, without creating a new String subsequent to
// each modification.
//
// The methods contained within this class do not return a new StringBuilder
// object unless specified otherwise. This class may be used in conjunction with the String
// class to carry out modifications upon strings.
[Serializable]
[System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
public sealed partial class StringBuilder : ISerializable
{
// A StringBuilder is internally represented as a linked list of blocks each of which holds
// a chunk of the string. It turns out string as a whole can also be represented as just a chunk,
// so that is what we do.
///
/// The character buffer for this chunk.
///
internal char[] m_ChunkChars;
///
/// The chunk that logically precedes this chunk.
///
internal StringBuilder m_ChunkPrevious;
///
/// The number of characters in this chunk.
/// This is the number of elements in that are in use, from the start of the buffer.
///
internal int m_ChunkLength;
///
/// The logical offset of this chunk's characters in the string it is a part of.
/// This is the sum of the number of characters in preceding blocks.
///
internal int m_ChunkOffset;
///
/// The maximum capacity this builder is allowed to have.
///
internal int m_MaxCapacity;
///
/// The default capacity of a .
///
internal const int DefaultCapacity = 16;
private const string CapacityField = "Capacity"; // Do not rename (binary serialization)
private const string MaxCapacityField = "m_MaxCapacity"; // Do not rename (binary serialization)
private const string StringValueField = "m_StringValue"; // Do not rename (binary serialization)
private const string ThreadIDField = "m_currentThread"; // Do not rename (binary serialization)
// We want to keep chunk arrays out of large object heap (< 85K bytes ~ 40K chars) to be sure.
// Making the maximum chunk size big means less allocation code called, but also more waste
// in unused characters and slower inserts / replaces (since you do need to slide characters over
// within a buffer).
internal const int MaxChunkSize = 8000;
///
/// Initializes a new instance of the class.
///
public StringBuilder()
{
m_MaxCapacity = int.MaxValue;
m_ChunkChars = new char[DefaultCapacity];
}
///
/// Initializes a new instance of the class.
///
/// The initial capacity of this builder.
public StringBuilder(int capacity)
: this(capacity, int.MaxValue)
{
}
///
/// Initializes a new instance of the class.
///
/// The initial contents of this builder.
public StringBuilder(string value)
: this(value, DefaultCapacity)
{
}
///
/// Initializes a new instance of the class.
///
/// The initial contents of this builder.
/// The initial capacity of this builder.
public StringBuilder(string value, int capacity)
: this(value, 0, value?.Length ?? 0, capacity)
{
}
///
/// Initializes a new instance of the class.
///
/// The initial contents of this builder.
/// The index to start in .
/// The number of characters to read in .
/// The initial capacity of this builder.
public StringBuilder(string value, int startIndex, int length, int capacity)
{
if (capacity < 0)
{
throw new ArgumentOutOfRangeException(nameof(capacity), SR.Format(SR.ArgumentOutOfRange_MustBePositive, nameof(capacity)));
}
if (length < 0)
{
throw new ArgumentOutOfRangeException(nameof(length), SR.Format(SR.ArgumentOutOfRange_MustBeNonNegNum, nameof(length)));
}
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
}
if (value == null)
{
value = string.Empty;
}
if (startIndex > value.Length - length)
{
throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_IndexLength);
}
m_MaxCapacity = int.MaxValue;
if (capacity == 0)
{
capacity = DefaultCapacity;
}
capacity = Math.Max(capacity, length);
m_ChunkChars = new char[capacity];
m_ChunkLength = length;
unsafe
{
fixed (char* sourcePtr = value)
{
ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length);
}
}
}
///
/// Initializes a new instance of the class.
///
/// The initial capacity of this builder.
/// The maximum capacity of this builder.
public StringBuilder(int capacity, int maxCapacity)
{
if (capacity > maxCapacity)
{
throw new ArgumentOutOfRangeException(nameof(capacity), SR.ArgumentOutOfRange_Capacity);
}
if (maxCapacity < 1)
{
throw new ArgumentOutOfRangeException(nameof(maxCapacity), SR.ArgumentOutOfRange_SmallMaxCapacity);
}
if (capacity < 0)
{
throw new ArgumentOutOfRangeException(nameof(capacity), SR.Format(SR.ArgumentOutOfRange_MustBePositive, nameof(capacity)));
}
if (capacity == 0)
{
capacity = Math.Min(DefaultCapacity, maxCapacity);
}
m_MaxCapacity = maxCapacity;
m_ChunkChars = new char[capacity];
}
private StringBuilder(SerializationInfo info, StreamingContext context)
{
if (info == null)
{
throw new ArgumentNullException(nameof(info));
}
int persistedCapacity = 0;
string persistedString = null;
int persistedMaxCapacity = int.MaxValue;
bool capacityPresent = false;
// Get the data
SerializationInfoEnumerator enumerator = info.GetEnumerator();
while (enumerator.MoveNext())
{
switch (enumerator.Name)
{
case MaxCapacityField:
persistedMaxCapacity = info.GetInt32(MaxCapacityField);
break;
case StringValueField:
persistedString = info.GetString(StringValueField);
break;
case CapacityField:
persistedCapacity = info.GetInt32(CapacityField);
capacityPresent = true;
break;
default:
// Ignore other fields for forwards-compatibility.
break;
}
}
// Check values and set defaults
if (persistedString == null)
{
persistedString = string.Empty;
}
if (persistedMaxCapacity < 1 || persistedString.Length > persistedMaxCapacity)
{
throw new SerializationException(SR.Serialization_StringBuilderMaxCapacity);
}
if (!capacityPresent)
{
// StringBuilder in V1.X did not persist the Capacity, so this is a valid legacy code path.
persistedCapacity = Math.Min(Math.Max(DefaultCapacity, persistedString.Length), persistedMaxCapacity);
}
if (persistedCapacity < 0 || persistedCapacity < persistedString.Length || persistedCapacity > persistedMaxCapacity)
{
throw new SerializationException(SR.Serialization_StringBuilderCapacity);
}
// Assign
m_MaxCapacity = persistedMaxCapacity;
m_ChunkChars = new char[persistedCapacity];
persistedString.CopyTo(0, m_ChunkChars, 0, persistedString.Length);
m_ChunkLength = persistedString.Length;
m_ChunkPrevious = null;
AssertInvariants();
}
void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
{
if (info == null)
{
throw new ArgumentNullException(nameof(info));
}
AssertInvariants();
info.AddValue(MaxCapacityField, m_MaxCapacity);
info.AddValue(CapacityField, Capacity);
info.AddValue(StringValueField, ToString());
// Note: persist "m_currentThread" to be compatible with old versions
info.AddValue(ThreadIDField, 0);
}
[System.Diagnostics.Conditional("DEBUG")]
private void AssertInvariants()
{
Debug.Assert(m_ChunkOffset + m_ChunkChars.Length >= m_ChunkOffset, "The length of the string is greater than int.MaxValue.");
StringBuilder currentBlock = this;
int maxCapacity = this.m_MaxCapacity;
for (;;)
{
// All blocks have the same max capacity.
Debug.Assert(currentBlock.m_MaxCapacity == maxCapacity);
Debug.Assert(currentBlock.m_ChunkChars != null);
Debug.Assert(currentBlock.m_ChunkLength <= currentBlock.m_ChunkChars.Length);
Debug.Assert(currentBlock.m_ChunkLength >= 0);
Debug.Assert(currentBlock.m_ChunkOffset >= 0);
StringBuilder prevBlock = currentBlock.m_ChunkPrevious;
if (prevBlock == null)
{
Debug.Assert(currentBlock.m_ChunkOffset == 0);
break;
}
// There are no gaps in the blocks.
Debug.Assert(currentBlock.m_ChunkOffset == prevBlock.m_ChunkOffset + prevBlock.m_ChunkLength);
currentBlock = prevBlock;
}
}
public int Capacity
{
get { return m_ChunkChars.Length + m_ChunkOffset; }
set
{
if (value < 0)
{
throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_NegativeCapacity);
}
if (value > MaxCapacity)
{
throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_Capacity);
}
if (value < Length)
{
throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_SmallCapacity);
}
if (Capacity != value)
{
int newLen = value - m_ChunkOffset;
char[] newArray = new char[newLen];
Array.Copy(m_ChunkChars, 0, newArray, 0, m_ChunkLength);
m_ChunkChars = newArray;
}
}
}
///
/// Gets the maximum capacity this builder is allowed to have.
///
public int MaxCapacity => m_MaxCapacity;
///
/// Ensures that the capacity of this builder is at least the specified value.
///
/// The new capacity for this builder.
///
/// If is less than or equal to the current capacity of
/// this builder, the capacity remains unchanged.
///
public int EnsureCapacity(int capacity)
{
if (capacity < 0)
{
throw new ArgumentOutOfRangeException(nameof(capacity), SR.ArgumentOutOfRange_NegativeCapacity);
}
if (Capacity < capacity)
Capacity = capacity;
return Capacity;
}
public override string ToString()
{
AssertInvariants();
if (Length == 0)
{
return string.Empty;
}
string result = string.FastAllocateString(Length);
StringBuilder chunk = this;
unsafe
{
fixed (char* destinationPtr = result)
{
do
{
if (chunk.m_ChunkLength > 0)
{
// Copy these into local variables so that they are stable even in the presence of race conditions
char[] sourceArray = chunk.m_ChunkChars;
int chunkOffset = chunk.m_ChunkOffset;
int chunkLength = chunk.m_ChunkLength;
// Check that we will not overrun our boundaries.
if ((uint)(chunkLength + chunkOffset) <= (uint)result.Length && (uint)chunkLength <= (uint)sourceArray.Length)
{
fixed (char* sourcePtr = &sourceArray[0])
string.wstrcpy(destinationPtr + chunkOffset, sourcePtr, chunkLength);
}
else
{
throw new ArgumentOutOfRangeException(nameof(chunkLength), SR.ArgumentOutOfRange_Index);
}
}
chunk = chunk.m_ChunkPrevious;
}
while (chunk != null);
return result;
}
}
}
///
/// Creates a string from a substring of this builder.
///
/// The index to start in this builder.
/// The number of characters to read in this builder.
public string ToString(int startIndex, int length)
{
int currentLength = this.Length;
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
}
if (startIndex > currentLength)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndexLargerThanLength);
}
if (length < 0)
{
throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_NegativeLength);
}
if (startIndex > currentLength - length)
{
throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_IndexLength);
}
AssertInvariants();
string result = string.FastAllocateString(length);
unsafe
{
fixed (char* destinationPtr = result)
{
this.CopyTo(startIndex, new Span(destinationPtr, length), length);
return result;
}
}
}
public StringBuilder Clear()
{
this.Length = 0;
return this;
}
///
/// Gets or sets the length of this builder.
///
public int Length
{
get
{
return m_ChunkOffset + m_ChunkLength;
}
set
{
//If the new length is less than 0 or greater than our Maximum capacity, bail.
if (value < 0)
{
throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_NegativeLength);
}
if (value > MaxCapacity)
{
throw new ArgumentOutOfRangeException(nameof(value), SR.ArgumentOutOfRange_SmallCapacity);
}
if (value == 0 && m_ChunkPrevious == null)
{
m_ChunkLength = 0;
m_ChunkOffset = 0;
return;
}
int delta = value - Length;
if (delta > 0)
{
// Pad ourselves with null characters.
Append('\0', delta);
}
else
{
StringBuilder chunk = FindChunkForIndex(value);
if (chunk != this)
{
// Avoid possible infinite capacity growth. See https://github.com/dotnet/coreclr/pull/16926
int capacityToPreserve = Math.Min(Capacity, Math.Max(Length * 6 / 5, m_ChunkChars.Length));
int newLen = capacityToPreserve - chunk.m_ChunkOffset;
if (newLen > chunk.m_ChunkChars.Length)
{
// We crossed a chunk boundary when reducing the Length. We must replace this middle-chunk with a new larger chunk,
// to ensure the capacity we want is preserved.
char[] newArray = new char[newLen];
Array.Copy(chunk.m_ChunkChars, 0, newArray, 0, chunk.m_ChunkLength);
m_ChunkChars = newArray;
}
else
{
// Special case where the capacity we want to keep corresponds exactly to the size of the content.
// Just take ownership of the array.
Debug.Assert(newLen == chunk.m_ChunkChars.Length, "The new chunk should be larger or equal to the one it is replacing.");
m_ChunkChars = chunk.m_ChunkChars;
}
m_ChunkPrevious = chunk.m_ChunkPrevious;
m_ChunkOffset = chunk.m_ChunkOffset;
}
m_ChunkLength = value - chunk.m_ChunkOffset;
AssertInvariants();
}
Debug.Assert(Length == value, "Something went wrong setting Length.");
}
}
[IndexerName("Chars")]
public char this[int index]
{
get
{
StringBuilder chunk = this;
for (;;)
{
int indexInBlock = index - chunk.m_ChunkOffset;
if (indexInBlock >= 0)
{
if (indexInBlock >= chunk.m_ChunkLength)
{
throw new IndexOutOfRangeException();
}
return chunk.m_ChunkChars[indexInBlock];
}
chunk = chunk.m_ChunkPrevious;
if (chunk == null)
{
throw new IndexOutOfRangeException();
}
}
}
set
{
StringBuilder chunk = this;
for (;;)
{
int indexInBlock = index - chunk.m_ChunkOffset;
if (indexInBlock >= 0)
{
if (indexInBlock >= chunk.m_ChunkLength)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
chunk.m_ChunkChars[indexInBlock] = value;
return;
}
chunk = chunk.m_ChunkPrevious;
if (chunk == null)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
}
}
}
///
/// GetChunks returns ChunkEnumerator that follows the IEnumerable pattern and
/// thus can be used in a C# 'foreach' statements to retreive the data in the StringBuilder
/// as chunks (ReadOnlyMemory) of characters. An example use is:
///
/// foreach (ReadOnlyMemory<char> chunk in sb.GetChunks())
/// foreach(char c in chunk.Span)
/// { /* operation on c }
///
/// It is undefined what happens if the StringBuilder is modified while the chunk
/// enumeration is incomplete. StringBuilder is also not thread-safe, so operating
/// on it with concurrent threads is illegal. Finally the ReadOnlyMemory chunks returned
/// are NOT guarenteed to remain unchanged if the StringBuilder is modified, so do
/// not cache them for later use either. This API's purpose is efficiently extracting
/// the data of a CONSTANT StringBuilder.
///
/// Creating a ReadOnlySpan from a ReadOnlyMemory (the .Span property) is expensive
/// compared to the fetching of the character, so create a local variable for the SPAN
/// if you need to use it in a nested for statement. For example
///
/// foreach (ReadOnlyMemory<char> chunk in sb.GetChunks())
/// {
/// var span = chunk.Span;
/// for(int i = 0; i < span.Length; i++)
/// { /* operation on span[i] */ }
/// }
///
public ChunkEnumerator GetChunks() => new ChunkEnumerator(this);
///
/// ChunkEnumerator supports both the IEnumerable and IEnumerator pattern so foreach
/// works (see GetChunks). It needs to be public (so the compiler can use it
/// when building a foreach statement) but users typically don't use it explicitly.
/// (which is why it is a nested type).
///
public struct ChunkEnumerator
{
private readonly StringBuilder _firstChunk; // The first Stringbuilder chunk (which is the end of the logical string)
private StringBuilder _currentChunk; // The chunk that this enumerator is currently returning (Current).
private readonly ManyChunkInfo _manyChunks; // Only used for long string builders with many chunks (see constructor)
///
/// Implement IEnumerable.GetEnumerator() to return 'this' as the IEnumerator
///
[ComponentModel.EditorBrowsable(ComponentModel.EditorBrowsableState.Never)] // Only here to make foreach work
public ChunkEnumerator GetEnumerator() { return this; }
///
/// Implements the IEnumerator pattern.
///
public bool MoveNext()
{
if (_currentChunk == _firstChunk)
return false;
if (_manyChunks != null)
return _manyChunks.MoveNext(ref _currentChunk);
StringBuilder next = _firstChunk;
while (next.m_ChunkPrevious != _currentChunk)
next = next.m_ChunkPrevious;
_currentChunk = next;
return true;
}
///
/// Implements the IEnumerator pattern.
///
public ReadOnlyMemory Current => new ReadOnlyMemory(_currentChunk.m_ChunkChars, 0, _currentChunk.m_ChunkLength);
#region private
internal ChunkEnumerator(StringBuilder stringBuilder)
{
Debug.Assert(stringBuilder != null);
_firstChunk = stringBuilder;
_currentChunk = null; // MoveNext will find the last chunk if we do this.
_manyChunks = null;
// There is a performance-vs-allocation tradeoff. Because the chunks
// are a linked list with each chunk pointing to its PREDECESSOR, walking
// the list FORWARD is not efficient. If there are few chunks (< 8) we
// simply scan from the start each time, and tolerate the N*N behavior.
// However above this size, we allocate an array to hold pointers to all
// the chunks and we can be efficient for large N.
int chunkCount = ChunkCount(stringBuilder);
if (8 < chunkCount)
_manyChunks = new ManyChunkInfo(stringBuilder, chunkCount);
}
private static int ChunkCount(StringBuilder stringBuilder)
{
int ret = 0;
while (stringBuilder != null)
{
ret++;
stringBuilder = stringBuilder.m_ChunkPrevious;
}
return ret;
}
///
/// Used to hold all the chunks indexes when you have many chunks.
///
private class ManyChunkInfo
{
private readonly StringBuilder[] _chunks; // These are in normal order (first chunk first)
private int _chunkPos;
public bool MoveNext(ref StringBuilder current)
{
int pos = ++_chunkPos;
if (_chunks.Length <= pos)
return false;
current = _chunks[pos];
return true;
}
public ManyChunkInfo(StringBuilder stringBuilder, int chunkCount)
{
_chunks = new StringBuilder[chunkCount];
while (0 <= --chunkCount)
{
Debug.Assert(stringBuilder != null);
_chunks[chunkCount] = stringBuilder;
stringBuilder = stringBuilder.m_ChunkPrevious;
}
_chunkPos = -1;
}
}
#endregion
}
///
/// Appends a character 0 or more times to the end of this builder.
///
/// The character to append.
/// The number of times to append .
public StringBuilder Append(char value, int repeatCount)
{
if (repeatCount < 0)
{
throw new ArgumentOutOfRangeException(nameof(repeatCount), SR.ArgumentOutOfRange_NegativeCount);
}
if (repeatCount == 0)
{
return this;
}
// this is where we can check if the repeatCount will put us over m_MaxCapacity
// We are doing the check here to prevent the corruption of the StringBuilder.
int newLength = Length + repeatCount;
if (newLength > m_MaxCapacity || newLength < repeatCount)
{
throw new ArgumentOutOfRangeException(nameof(repeatCount), SR.ArgumentOutOfRange_LengthGreaterThanCapacity);
}
int index = m_ChunkLength;
while (repeatCount > 0)
{
if (index < m_ChunkChars.Length)
{
m_ChunkChars[index++] = value;
--repeatCount;
}
else
{
m_ChunkLength = index;
ExpandByABlock(repeatCount);
Debug.Assert(m_ChunkLength == 0);
index = 0;
}
}
m_ChunkLength = index;
AssertInvariants();
return this;
}
///
/// Appends a range of characters to the end of this builder.
///
/// The characters to append.
/// The index to start in .
/// The number of characters to read in .
public StringBuilder Append(char[] value, int startIndex, int charCount)
{
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_GenericPositive);
}
if (charCount < 0)
{
throw new ArgumentOutOfRangeException(nameof(charCount), SR.ArgumentOutOfRange_GenericPositive);
}
if (value == null)
{
if (startIndex == 0 && charCount == 0)
{
return this;
}
throw new ArgumentNullException(nameof(value));
}
if (charCount > value.Length - startIndex)
{
throw new ArgumentOutOfRangeException(nameof(charCount), SR.ArgumentOutOfRange_Index);
}
if (charCount == 0)
{
return this;
}
unsafe
{
fixed (char* valueChars = &value[startIndex])
{
Append(valueChars, charCount);
return this;
}
}
}
///
/// Appends a string to the end of this builder.
///
/// The string to append.
public StringBuilder Append(string value)
{
if (value != null)
{
// We could have just called AppendHelper here; this is a hand-specialization of that code.
char[] chunkChars = m_ChunkChars;
int chunkLength = m_ChunkLength;
int valueLen = value.Length;
int newCurrentIndex = chunkLength + valueLen;
if (newCurrentIndex < chunkChars.Length) // Use strictly < to avoid issues if count == 0, newIndex == length
{
if (valueLen <= 2)
{
if (valueLen > 0)
chunkChars[chunkLength] = value[0];
if (valueLen > 1)
chunkChars[chunkLength + 1] = value[1];
}
else
{
unsafe
{
fixed (char* valuePtr = value)
fixed (char* destPtr = &chunkChars[chunkLength])
{
string.wstrcpy(destPtr, valuePtr, valueLen);
}
}
}
m_ChunkLength = newCurrentIndex;
}
else
{
AppendHelper(value);
}
}
return this;
}
// We put this fixed in its own helper to avoid the cost of zero-initing `valueChars` in the
// case we don't actually use it.
private void AppendHelper(string value)
{
unsafe
{
fixed (char* valueChars = value)
{
Append(valueChars, value.Length);
}
}
}
///
/// Appends part of a string to the end of this builder.
///
/// The string to append.
/// The index to start in .
/// The number of characters to read in .
public StringBuilder Append(string value, int startIndex, int count)
{
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
if (count < 0)
{
throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_GenericPositive);
}
if (value == null)
{
if (startIndex == 0 && count == 0)
{
return this;
}
throw new ArgumentNullException(nameof(value));
}
if (count == 0)
{
return this;
}
if (startIndex > value.Length - count)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
unsafe
{
fixed (char* valueChars = value)
{
Append(valueChars + startIndex, count);
return this;
}
}
}
public StringBuilder Append(StringBuilder value)
{
if (value != null && value.Length != 0)
{
return AppendCore(value, 0, value.Length);
}
return this;
}
public StringBuilder Append(StringBuilder value, int startIndex, int count)
{
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
if (count < 0)
{
throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_GenericPositive);
}
if (value == null)
{
if (startIndex == 0 && count == 0)
{
return this;
}
throw new ArgumentNullException(nameof(value));
}
if (count == 0)
{
return this;
}
if (count > value.Length - startIndex)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
return AppendCore(value, startIndex, count);
}
private StringBuilder AppendCore(StringBuilder value, int startIndex, int count)
{
if (value == this)
return Append(value.ToString(startIndex, count));
int newLength = Length + count;
if ((uint)newLength > (uint)m_MaxCapacity)
{
throw new ArgumentOutOfRangeException(nameof(Capacity), SR.ArgumentOutOfRange_Capacity);
}
while (count > 0)
{
int length = Math.Min(m_ChunkChars.Length - m_ChunkLength, count);
if (length == 0)
{
ExpandByABlock(count);
length = Math.Min(m_ChunkChars.Length - m_ChunkLength, count);
}
value.CopyTo(startIndex, new Span(m_ChunkChars, m_ChunkLength, length), length);
m_ChunkLength += length;
startIndex += length;
count -= length;
}
return this;
}
public StringBuilder AppendLine() => Append(Environment.NewLine);
public StringBuilder AppendLine(string value)
{
Append(value);
return Append(Environment.NewLine);
}
public void CopyTo(int sourceIndex, char[] destination, int destinationIndex, int count)
{
if (destination == null)
{
throw new ArgumentNullException(nameof(destination));
}
if (destinationIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.Format(SR.ArgumentOutOfRange_MustBeNonNegNum, nameof(destinationIndex)));
}
if (destinationIndex > destination.Length - count)
{
throw new ArgumentException(SR.ArgumentOutOfRange_OffsetOut);
}
CopyTo(sourceIndex, new Span(destination).Slice(destinationIndex), count);
}
public void CopyTo(int sourceIndex, Span destination, int count)
{
if (count < 0)
{
throw new ArgumentOutOfRangeException(nameof(count), SR.Arg_NegativeArgCount);
}
if ((uint)sourceIndex > (uint)Length)
{
throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_Index);
}
if (sourceIndex > Length - count)
{
throw new ArgumentException(SR.Arg_LongerThanSrcString);
}
AssertInvariants();
StringBuilder chunk = this;
int sourceEndIndex = sourceIndex + count;
int curDestIndex = count;
while (count > 0)
{
int chunkEndIndex = sourceEndIndex - chunk.m_ChunkOffset;
if (chunkEndIndex >= 0)
{
chunkEndIndex = Math.Min(chunkEndIndex, chunk.m_ChunkLength);
int chunkCount = count;
int chunkStartIndex = chunkEndIndex - count;
if (chunkStartIndex < 0)
{
chunkCount += chunkStartIndex;
chunkStartIndex = 0;
}
curDestIndex -= chunkCount;
count -= chunkCount;
// We ensure that chunkStartIndex + chunkCount are within range of m_chunkChars as well as
// ensuring that curDestIndex + chunkCount are within range of destination
ThreadSafeCopy(chunk.m_ChunkChars, chunkStartIndex, destination, curDestIndex, chunkCount);
}
chunk = chunk.m_ChunkPrevious;
}
}
///
/// Inserts a string 0 or more times into this builder at the specified position.
///
/// The index to insert in this builder.
/// The string to insert.
/// The number of times to insert the string.
public StringBuilder Insert(int index, string value, int count)
{
if (count < 0)
{
throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NeedNonNegNum);
}
int currentLength = Length;
if ((uint)index > (uint)currentLength)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
if (string.IsNullOrEmpty(value) || count == 0)
{
return this;
}
// Ensure we don't insert more chars than we can hold, and we don't
// have any integer overflow in our new length.
long insertingChars = (long)value.Length * count;
if (insertingChars > MaxCapacity - this.Length)
{
throw new OutOfMemoryException();
}
Debug.Assert(insertingChars + this.Length < int.MaxValue);
StringBuilder chunk;
int indexInChunk;
MakeRoom(index, (int)insertingChars, out chunk, out indexInChunk, false);
unsafe
{
fixed (char* valuePtr = value)
{
while (count > 0)
{
ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, valuePtr, value.Length);
--count;
}
return this;
}
}
}
///
/// Removes a range of characters from this builder.
///
///
/// This method does not reduce the capacity of this builder.
///
public StringBuilder Remove(int startIndex, int length)
{
if (length < 0)
{
throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_NegativeLength);
}
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
}
if (length > Length - startIndex)
{
throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_Index);
}
if (Length == length && startIndex == 0)
{
Length = 0;
return this;
}
if (length > 0)
{
StringBuilder chunk;
int indexInChunk;
Remove(startIndex, length, out chunk, out indexInChunk);
}
return this;
}
public StringBuilder Append(bool value) => Append(value.ToString());
public StringBuilder Append(char value)
{
if (m_ChunkLength < m_ChunkChars.Length)
{
m_ChunkChars[m_ChunkLength++] = value;
}
else
{
Append(value, 1);
}
return this;
}
[CLSCompliant(false)]
public StringBuilder Append(sbyte value) => AppendSpanFormattable(value);
public StringBuilder Append(byte value) => AppendSpanFormattable(value);
public StringBuilder Append(short value) => AppendSpanFormattable(value);
public StringBuilder Append(int value) => AppendSpanFormattable(value);
public StringBuilder Append(long value) => AppendSpanFormattable(value);
public StringBuilder Append(float value) => AppendSpanFormattable(value);
public StringBuilder Append(double value) => AppendSpanFormattable(value);
public StringBuilder Append(decimal value) => AppendSpanFormattable(value);
[CLSCompliant(false)]
public StringBuilder Append(ushort value) => AppendSpanFormattable(value);
[CLSCompliant(false)]
public StringBuilder Append(uint value) => AppendSpanFormattable(value);
[CLSCompliant(false)]
public StringBuilder Append(ulong value) => AppendSpanFormattable(value);
private StringBuilder AppendSpanFormattable(T value) where T : ISpanFormattable
{
if (value.TryFormat(RemainingCurrentChunk, out int charsWritten, format: default, provider: null))
{
m_ChunkLength += charsWritten;
return this;
}
return Append(value.ToString());
}
public StringBuilder Append(object value) => (value == null) ? this : Append(value.ToString());
public StringBuilder Append(char[] value)
{
if (value?.Length > 0)
{
unsafe
{
fixed (char* valueChars = &value[0])
{
Append(valueChars, value.Length);
}
}
}
return this;
}
public StringBuilder Append(ReadOnlySpan value)
{
if (value.Length > 0)
{
unsafe
{
fixed (char* valueChars = &MemoryMarshal.GetReference(value))
{
Append(valueChars, value.Length);
}
}
}
return this;
}
public StringBuilder Append(ReadOnlyMemory value) => Append(value.Span);
#region AppendJoin
public unsafe StringBuilder AppendJoin(string separator, params object[] values)
{
separator = separator ?? string.Empty;
fixed (char* pSeparator = separator)
{
return AppendJoinCore(pSeparator, separator.Length, values);
}
}
public unsafe StringBuilder AppendJoin(string separator, IEnumerable values)
{
separator = separator ?? string.Empty;
fixed (char* pSeparator = separator)
{
return AppendJoinCore(pSeparator, separator.Length, values);
}
}
public unsafe StringBuilder AppendJoin(string separator, params string[] values)
{
separator = separator ?? string.Empty;
fixed (char* pSeparator = separator)
{
return AppendJoinCore(pSeparator, separator.Length, values);
}
}
public unsafe StringBuilder AppendJoin(char separator, params object[] values)
{
return AppendJoinCore(&separator, 1, values);
}
public unsafe StringBuilder AppendJoin(char separator, IEnumerable values)
{
return AppendJoinCore(&separator, 1, values);
}
public unsafe StringBuilder AppendJoin(char separator, params string[] values)
{
return AppendJoinCore(&separator, 1, values);
}
private unsafe StringBuilder AppendJoinCore(char* separator, int separatorLength, IEnumerable values)
{
Debug.Assert(separator != null);
Debug.Assert(separatorLength >= 0);
if (values == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.values);
}
using (IEnumerator en = values.GetEnumerator())
{
if (!en.MoveNext())
{
return this;
}
var value = en.Current;
if (value != null)
{
Append(value.ToString());
}
while (en.MoveNext())
{
Append(separator, separatorLength);
value = en.Current;
if (value != null)
{
Append(value.ToString());
}
}
}
return this;
}
private unsafe StringBuilder AppendJoinCore(char* separator, int separatorLength, T[] values)
{
if (values == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.values);
}
if (values.Length == 0)
{
return this;
}
if (values[0] != null)
{
Append(values[0].ToString());
}
for (int i = 1; i < values.Length; i++)
{
Append(separator, separatorLength);
if (values[i] != null)
{
Append(values[i].ToString());
}
}
return this;
}
#endregion
public StringBuilder Insert(int index, string value)
{
if ((uint)index > (uint)Length)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
if (value != null)
{
unsafe
{
fixed (char* sourcePtr = value)
Insert(index, sourcePtr, value.Length);
}
}
return this;
}
public StringBuilder Insert(int index, bool value) => Insert(index, value.ToString(), 1);
[CLSCompliant(false)]
public StringBuilder Insert(int index, sbyte value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, byte value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, short value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, char value)
{
unsafe
{
Insert(index, &value, 1);
}
return this;
}
public StringBuilder Insert(int index, char[] value)
{
if ((uint)index > (uint)Length)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
if (value != null)
Insert(index, value, 0, value.Length);
return this;
}
public StringBuilder Insert(int index, char[] value, int startIndex, int charCount)
{
int currentLength = Length;
if ((uint)index > (uint)currentLength)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
if (value == null)
{
if (startIndex == 0 && charCount == 0)
{
return this;
}
throw new ArgumentNullException(nameof(value), SR.ArgumentNull_String);
}
if (startIndex < 0)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_StartIndex);
}
if (charCount < 0)
{
throw new ArgumentOutOfRangeException(nameof(charCount), SR.ArgumentOutOfRange_GenericPositive);
}
if (startIndex > value.Length - charCount)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
if (charCount > 0)
{
unsafe
{
fixed (char* sourcePtr = &value[startIndex])
Insert(index, sourcePtr, charCount);
}
}
return this;
}
public StringBuilder Insert(int index, int value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, long value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, float value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, double value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, decimal value) => Insert(index, value.ToString(), 1);
[CLSCompliant(false)]
public StringBuilder Insert(int index, ushort value) => Insert(index, value.ToString(), 1);
[CLSCompliant(false)]
public StringBuilder Insert(int index, uint value) => Insert(index, value.ToString(), 1);
[CLSCompliant(false)]
public StringBuilder Insert(int index, ulong value) => Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, object value) => (value == null) ? this : Insert(index, value.ToString(), 1);
public StringBuilder Insert(int index, ReadOnlySpan value)
{
if ((uint)index > (uint)Length)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
if (value.Length > 0)
{
unsafe
{
fixed (char* sourcePtr = &MemoryMarshal.GetReference(value))
Insert(index, sourcePtr, value.Length);
}
}
return this;
}
public StringBuilder AppendFormat(string format, object arg0) => AppendFormatHelper(null, format, new ParamsArray(arg0));
public StringBuilder AppendFormat(string format, object arg0, object arg1) => AppendFormatHelper(null, format, new ParamsArray(arg0, arg1));
public StringBuilder AppendFormat(string format, object arg0, object arg1, object arg2) => AppendFormatHelper(null, format, new ParamsArray(arg0, arg1, arg2));
public StringBuilder AppendFormat(string format, params object[] args)
{
if (args == null)
{
// To preserve the original exception behavior, throw an exception about format if both
// args and format are null. The actual null check for format is in AppendFormatHelper.
string paramName = (format == null) ? nameof(format) : nameof(args);
throw new ArgumentNullException(paramName);
}
return AppendFormatHelper(null, format, new ParamsArray(args));
}
public StringBuilder AppendFormat(IFormatProvider provider, string format, object arg0) => AppendFormatHelper(provider, format, new ParamsArray(arg0));
public StringBuilder AppendFormat(IFormatProvider provider, string format, object arg0, object arg1) => AppendFormatHelper(provider, format, new ParamsArray(arg0, arg1));
public StringBuilder AppendFormat(IFormatProvider provider, string format, object arg0, object arg1, object arg2) => AppendFormatHelper(provider, format, new ParamsArray(arg0, arg1, arg2));
public StringBuilder AppendFormat(IFormatProvider provider, string format, params object[] args)
{
if (args == null)
{
// To preserve the original exception behavior, throw an exception about format if both
// args and format are null. The actual null check for format is in AppendFormatHelper.
string paramName = (format == null) ? nameof(format) : nameof(args);
throw new ArgumentNullException(paramName);
}
return AppendFormatHelper(provider, format, new ParamsArray(args));
}
private static void FormatError()
{
throw new FormatException(SR.Format_InvalidString);
}
// Undocumented exclusive limits on the range for Argument Hole Index and Argument Hole Alignment.
private const int IndexLimit = 1000000; // Note: 0 <= ArgIndex < IndexLimit
private const int WidthLimit = 1000000; // Note: -WidthLimit < ArgAlign < WidthLimit
internal StringBuilder AppendFormatHelper(IFormatProvider provider, string format, ParamsArray args)
{
if (format == null)
{
throw new ArgumentNullException(nameof(format));
}
int pos = 0;
int len = format.Length;
char ch = '\x0';
StringBuilder unescapedItemFormat = null;
ICustomFormatter cf = null;
if (provider != null)
{
cf = (ICustomFormatter)provider.GetFormat(typeof(ICustomFormatter));
}
while (true)
{
while (pos < len)
{
ch = format[pos];
pos++;
// Is it a closing brace?
if (ch == '}')
{
// Check next character (if there is one) to see if it is escaped. eg }}
if (pos < len && format[pos] == '}')
pos++;
else
// Otherwise treat it as an error (Mismatched closing brace)
FormatError();
}
// Is it a opening brace?
if (ch == '{')
{
// Check next character (if there is one) to see if it is escaped. eg {{
if (pos < len && format[pos] == '{')
pos++;
else
{
// Otherwise treat it as the opening brace of an Argument Hole.
pos--;
break;
}
}
// If it neither then treat the character as just text.
Append(ch);
}
//
// Start of parsing of Argument Hole.
// Argument Hole ::= { Index (, WS* Alignment WS*)? (: Formatting)? }
//
if (pos == len) break;
//
// Start of parsing required Index parameter.
// Index ::= ('0'-'9')+ WS*
//
pos++;
// If reached end of text then error (Unexpected end of text)
// or character is not a digit then error (Unexpected Character)
if (pos == len || (ch = format[pos]) < '0' || ch > '9') FormatError();
int index = 0;
do
{
index = index * 10 + ch - '0';
pos++;
// If reached end of text then error (Unexpected end of text)
if (pos == len) FormatError();
ch = format[pos];
// so long as character is digit and value of the index is less than 1000000 ( index limit )
}
while (ch >= '0' && ch <= '9' && index < IndexLimit);
// If value of index is not within the range of the arguments passed in then error (Index out of range)
if (index >= args.Length) throw new FormatException(SR.Format_IndexOutOfRange);
// Consume optional whitespace.
while (pos < len && (ch = format[pos]) == ' ') pos++;
// End of parsing index parameter.
//
// Start of parsing of optional Alignment
// Alignment ::= comma WS* minus? ('0'-'9')+ WS*
//
bool leftJustify = false;
int width = 0;
// Is the character a comma, which indicates the start of alignment parameter.
if (ch == ',')
{
pos++;
// Consume Optional whitespace
while (pos < len && format[pos] == ' ') pos++;
// If reached the end of the text then error (Unexpected end of text)
if (pos == len) FormatError();
// Is there a minus sign?
ch = format[pos];
if (ch == '-')
{
// Yes, then alignment is left justified.
leftJustify = true;
pos++;
// If reached end of text then error (Unexpected end of text)
if (pos == len) FormatError();
ch = format[pos];
}
// If current character is not a digit then error (Unexpected character)
if (ch < '0' || ch > '9') FormatError();
// Parse alignment digits.
do
{
width = width * 10 + ch - '0';
pos++;
// If reached end of text then error. (Unexpected end of text)
if (pos == len) FormatError();
ch = format[pos];
// So long a current character is a digit and the value of width is less than 100000 ( width limit )
}
while (ch >= '0' && ch <= '9' && width < WidthLimit);
// end of parsing Argument Alignment
}
// Consume optional whitespace
while (pos < len && (ch = format[pos]) == ' ') pos++;
//
// Start of parsing of optional formatting parameter.
//
object arg = args[index];
string itemFormat = null;
ReadOnlySpan itemFormatSpan = default; // used if itemFormat is null
// Is current character a colon? which indicates start of formatting parameter.
if (ch == ':')
{
pos++;
int startPos = pos;
while (true)
{
// If reached end of text then error. (Unexpected end of text)
if (pos == len) FormatError();
ch = format[pos];
pos++;
// Is character a opening or closing brace?
if (ch == '}' || ch == '{')
{
if (ch == '{')
{
// Yes, is next character also a opening brace, then treat as escaped. eg {{
if (pos < len && format[pos] == '{')
pos++;
else
// Error Argument Holes can not be nested.
FormatError();
}
else
{
// Yes, is next character also a closing brace, then treat as escaped. eg }}
if (pos < len && format[pos] == '}')
pos++;
else
{
// No, then treat it as the closing brace of an Arg Hole.
pos--;
break;
}
}
// Reaching here means the brace has been escaped
// so we need to build up the format string in segments
if (unescapedItemFormat == null)
{
unescapedItemFormat = new StringBuilder();
}
unescapedItemFormat.Append(format, startPos, pos - startPos - 1);
startPos = pos;
}
}
if (unescapedItemFormat == null || unescapedItemFormat.Length == 0)
{
if (startPos != pos)
{
// There was no brace escaping, extract the item format as a single string
itemFormatSpan = format.AsSpan(startPos, pos - startPos);
}
}
else
{
unescapedItemFormat.Append(format, startPos, pos - startPos);
itemFormatSpan = itemFormat = unescapedItemFormat.ToString();
unescapedItemFormat.Clear();
}
}
// If current character is not a closing brace then error. (Unexpected Character)
if (ch != '}') FormatError();
// Construct the output for this arg hole.
pos++;
string s = null;
if (cf != null)
{
if (itemFormatSpan.Length != 0 && itemFormat == null)
{
itemFormat = new string(itemFormatSpan);
}
s = cf.Format(itemFormat, arg, provider);
}
if (s == null)
{
// If arg is ISpanFormattable and the beginning doesn't need padding,
// try formatting it into the remaining current chunk.
if (arg is ISpanFormattable spanFormattableArg &&
(leftJustify || width == 0) &&
spanFormattableArg.TryFormat(RemainingCurrentChunk, out int charsWritten, itemFormatSpan, provider))
{
m_ChunkLength += charsWritten;
// Pad the end, if needed.
int padding = width - charsWritten;
if (leftJustify && padding > 0) Append(' ', padding);
// Continue to parse other characters.
continue;
}
// Otherwise, fallback to trying IFormattable or calling ToString.
if (arg is IFormattable formattableArg)
{
if (itemFormatSpan.Length != 0 && itemFormat == null)
{
itemFormat = new string(itemFormatSpan);
}
s = formattableArg.ToString(itemFormat, provider);
}
else if (arg != null)
{
s = arg.ToString();
}
}
// Append it to the final output of the Format String.
if (s == null) s = string.Empty;
int pad = width - s.Length;
if (!leftJustify && pad > 0) Append(' ', pad);
Append(s);
if (leftJustify && pad > 0) Append(' ', pad);
// Continue to parse other characters.
}
return this;
}
///
/// Replaces all instances of one string with another in this builder.
///
/// The string to replace.
/// The string to replace with.
///
/// If is null, instances of
/// are removed from this builder.
///
public StringBuilder Replace(string oldValue, string newValue) => Replace(oldValue, newValue, 0, Length);
///
/// Determines if the contents of this builder are equal to the contents of another builder.
///
/// The other builder.
public bool Equals(StringBuilder sb)
{
if (sb == null)
return false;
if (Length != sb.Length)
return false;
if (sb == this)
return true;
StringBuilder thisChunk = this;
int thisChunkIndex = thisChunk.m_ChunkLength;
StringBuilder sbChunk = sb;
int sbChunkIndex = sbChunk.m_ChunkLength;
for (;;)
{
--thisChunkIndex;
--sbChunkIndex;
while (thisChunkIndex < 0)
{
thisChunk = thisChunk.m_ChunkPrevious;
if (thisChunk == null)
break;
thisChunkIndex = thisChunk.m_ChunkLength + thisChunkIndex;
}
while (sbChunkIndex < 0)
{
sbChunk = sbChunk.m_ChunkPrevious;
if (sbChunk == null)
break;
sbChunkIndex = sbChunk.m_ChunkLength + sbChunkIndex;
}
if (thisChunkIndex < 0)
return sbChunkIndex < 0;
if (sbChunkIndex < 0)
return false;
if (thisChunk.m_ChunkChars[thisChunkIndex] != sbChunk.m_ChunkChars[sbChunkIndex])
return false;
}
}
///
/// Determines if the contents of this builder are equal to the contents of .
///
/// The .
public bool Equals(ReadOnlySpan span)
{
if (span.Length != Length)
return false;
StringBuilder sbChunk = this;
int offset = 0;
do
{
int chunk_length = sbChunk.m_ChunkLength;
offset += chunk_length;
ReadOnlySpan chunk = new ReadOnlySpan(sbChunk.m_ChunkChars, 0, chunk_length);
if (!chunk.EqualsOrdinal(span.Slice(span.Length - offset, chunk_length)))
return false;
sbChunk = sbChunk.m_ChunkPrevious;
} while (sbChunk != null);
Debug.Assert(offset == Length);
return true;
}
///
/// Replaces all instances of one string with another in part of this builder.
///
/// The string to replace.
/// The string to replace with.
/// The index to start in this builder.
/// The number of characters to read in this builder.
///
/// If is null, instances of
/// are removed from this builder.
///
public StringBuilder Replace(string oldValue, string newValue, int startIndex, int count)
{
int currentLength = Length;
if ((uint)startIndex > (uint)currentLength)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
if (count < 0 || startIndex > currentLength - count)
{
throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Index);
}
if (oldValue == null)
{
throw new ArgumentNullException(nameof(oldValue));
}
if (oldValue.Length == 0)
{
throw new ArgumentException(SR.Argument_EmptyName, nameof(oldValue));
}
newValue = newValue ?? string.Empty;
int deltaLength = newValue.Length - oldValue.Length;
int[] replacements = null; // A list of replacement positions in a chunk to apply
int replacementsCount = 0;
// Find the chunk, indexInChunk for the starting point
StringBuilder chunk = FindChunkForIndex(startIndex);
int indexInChunk = startIndex - chunk.m_ChunkOffset;
while (count > 0)
{
// Look for a match in the chunk,indexInChunk pointer
if (StartsWith(chunk, indexInChunk, count, oldValue))
{
// Push it on the replacements array (with growth), we will do all replacements in a
// given chunk in one operation below (see ReplaceAllInChunk) so we don't have to slide
// many times.
if (replacements == null)
{
replacements = new int[5];
}
else if (replacementsCount >= replacements.Length)
{
Array.Resize(ref replacements, replacements.Length * 3 / 2 + 4); // Grow by ~1.5x, but more in the begining
}
replacements[replacementsCount++] = indexInChunk;
indexInChunk += oldValue.Length;
count -= oldValue.Length;
}
else
{
indexInChunk++;
--count;
}
if (indexInChunk >= chunk.m_ChunkLength || count == 0) // Have we moved out of the current chunk?
{
// Replacing mutates the blocks, so we need to convert to a logical index and back afterwards.
int index = indexInChunk + chunk.m_ChunkOffset;
int indexBeforeAdjustment = index;
// See if we accumulated any replacements, if so apply them.
ReplaceAllInChunk(replacements, replacementsCount, chunk, oldValue.Length, newValue);
// The replacement has affected the logical index. Adjust it.
index += ((newValue.Length - oldValue.Length) * replacementsCount);
replacementsCount = 0;
chunk = FindChunkForIndex(index);
indexInChunk = index - chunk.m_ChunkOffset;
Debug.Assert(chunk != null || count == 0, "Chunks ended prematurely!");
}
}
AssertInvariants();
return this;
}
///
/// Replaces all instances of one character with another in this builder.
///
/// The character to replace.
/// The character to replace with.
public StringBuilder Replace(char oldChar, char newChar)
{
return Replace(oldChar, newChar, 0, Length);
}
///
/// Replaces all instances of one character with another in this builder.
///
/// The character to replace.
/// The character to replace with.
/// The index to start in this builder.
/// The number of characters to read in this builder.
public StringBuilder Replace(char oldChar, char newChar, int startIndex, int count)
{
int currentLength = Length;
if ((uint)startIndex > (uint)currentLength)
{
throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
}
if (count < 0 || startIndex > currentLength - count)
{
throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Index);
}
int endIndex = startIndex + count;
StringBuilder chunk = this;
for (;;)
{
int endIndexInChunk = endIndex - chunk.m_ChunkOffset;
int startIndexInChunk = startIndex - chunk.m_ChunkOffset;
if (endIndexInChunk >= 0)
{
int curInChunk = Math.Max(startIndexInChunk, 0);
int endInChunk = Math.Min(chunk.m_ChunkLength, endIndexInChunk);
while (curInChunk < endInChunk)
{
if (chunk.m_ChunkChars[curInChunk] == oldChar)
chunk.m_ChunkChars[curInChunk] = newChar;
curInChunk++;
}
}
if (startIndexInChunk >= 0)
break;
chunk = chunk.m_ChunkPrevious;
}
AssertInvariants();
return this;
}
///
/// Appends a character buffer to this builder.
///
/// The pointer to the start of the buffer.
/// The number of characters in the buffer.
[CLSCompliant(false)]
public unsafe StringBuilder Append(char* value, int valueCount)
{
// We don't check null value as this case will throw null reference exception anyway
if (valueCount < 0)
{
throw new ArgumentOutOfRangeException(nameof(valueCount), SR.ArgumentOutOfRange_NegativeCount);
}
// this is where we can check if the valueCount will put us over m_MaxCapacity
// We are doing the check here to prevent the corruption of the StringBuilder.
int newLength = Length + valueCount;
if (newLength > m_MaxCapacity || newLength < valueCount)
{
throw new ArgumentOutOfRangeException(nameof(valueCount), SR.ArgumentOutOfRange_LengthGreaterThanCapacity);
}
// This case is so common we want to optimize for it heavily.
int newIndex = valueCount + m_ChunkLength;
if (newIndex <= m_ChunkChars.Length)
{
ThreadSafeCopy(value, m_ChunkChars, m_ChunkLength, valueCount);
m_ChunkLength = newIndex;
}
else
{
// Copy the first chunk
int firstLength = m_ChunkChars.Length - m_ChunkLength;
if (firstLength > 0)
{
ThreadSafeCopy(value, m_ChunkChars, m_ChunkLength, firstLength);
m_ChunkLength = m_ChunkChars.Length;
}
// Expand the builder to add another chunk.
int restLength = valueCount - firstLength;
ExpandByABlock(restLength);
Debug.Assert(m_ChunkLength == 0, "A new block was not created.");
// Copy the second chunk
ThreadSafeCopy(value + firstLength, m_ChunkChars, 0, restLength);
m_ChunkLength = restLength;
}
AssertInvariants();
return this;
}
///
/// Inserts a character buffer into this builder at the specified position.
///
/// The index to insert in this builder.
/// The pointer to the start of the buffer.
/// The number of characters in the buffer.
private unsafe void Insert(int index, char* value, int valueCount)
{
if ((uint)index > (uint)Length)
{
throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index);
}
if (valueCount > 0)
{
StringBuilder chunk;
int indexInChunk;
MakeRoom(index, valueCount, out chunk, out indexInChunk, false);
ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, value, valueCount);
}
}
///
/// Replaces strings at specified indices with a new string in a chunk.
///
/// The list of indices, relative to the beginning of the chunk, to remove at.
/// The number of replacements to make.
/// The source chunk.
/// The number of characters to remove at each replacement.
/// The string to insert at each replacement.
///
/// This routine is very efficient because it does replacements in bulk.
///
private void ReplaceAllInChunk(int[] replacements, int replacementsCount, StringBuilder sourceChunk, int removeCount, string value)
{
if (replacementsCount <= 0)
{
return;
}
unsafe
{
fixed (char* valuePtr = value)
{
// calculate the total amount of extra space or space needed for all the replacements.
long longDelta = (value.Length - removeCount) * (long)replacementsCount;
int delta = (int)longDelta;
if (delta != longDelta)
throw new OutOfMemoryException();
StringBuilder targetChunk = sourceChunk; // the target as we copy chars down
int targetIndexInChunk = replacements[0];
// Make the room needed for all the new characters if needed.
if (delta > 0)
MakeRoom(targetChunk.m_ChunkOffset + targetIndexInChunk, delta, out targetChunk, out targetIndexInChunk, true);
// We made certain that characters after the insertion point are not moved,
int i = 0;
for (;;)
{
// Copy in the new string for the ith replacement
ReplaceInPlaceAtChunk(ref targetChunk, ref targetIndexInChunk, valuePtr, value.Length);
int gapStart = replacements[i] + removeCount;
i++;
if (i >= replacementsCount)
{
break;
}
int gapEnd = replacements[i];
Debug.Assert(gapStart < sourceChunk.m_ChunkChars.Length, "gap starts at end of buffer. Should not happen");
Debug.Assert(gapStart <= gapEnd, "negative gap size");
Debug.Assert(gapEnd <= sourceChunk.m_ChunkLength, "gap too big");
if (delta != 0) // can skip the sliding of gaps if source an target string are the same size.
{
// Copy the gap data between the current replacement and the next replacement
fixed (char* sourcePtr = &sourceChunk.m_ChunkChars[gapStart])
ReplaceInPlaceAtChunk(ref targetChunk, ref targetIndexInChunk, sourcePtr, gapEnd - gapStart);
}
else
{
targetIndexInChunk += gapEnd - gapStart;
Debug.Assert(targetIndexInChunk <= targetChunk.m_ChunkLength, "gap not in chunk");
}
}
// Remove extra space if necessary.
if (delta < 0)
Remove(targetChunk.m_ChunkOffset + targetIndexInChunk, -delta, out targetChunk, out targetIndexInChunk);
}
}
}
///
/// Returns a value indicating whether a substring of a builder starts with a specified prefix.
///
/// The chunk in which the substring starts.
/// The index in at which the substring starts.
/// The logical count of the substring.
/// The prefix.
private bool StartsWith(StringBuilder chunk, int indexInChunk, int count, string value)
{
for (int i = 0; i < value.Length; i++)
{
if (count == 0)
{
return false;
}
if (indexInChunk >= chunk.m_ChunkLength)
{
chunk = Next(chunk);
if (chunk == null)
return false;
indexInChunk = 0;
}
if (value[i] != chunk.m_ChunkChars[indexInChunk])
{
return false;
}
indexInChunk++;
--count;
}
return true;
}
///
/// Replaces characters at a specified location with the contents of a character buffer.
/// This function is the logical equivalent of memcpy.
///
///
/// The chunk in which to start replacing characters.
/// Receives the chunk in which character replacement ends.
///
///
/// The index in to start replacing characters at.
/// Receives the index at which character replacement ends.
///
/// The pointer to the start of the character buffer.
/// The number of characters in the buffer.
private unsafe void ReplaceInPlaceAtChunk(ref StringBuilder chunk, ref int indexInChunk, char* value, int count)
{
if (count != 0)
{
for (;;)
{
int lengthInChunk = chunk.m_ChunkLength - indexInChunk;
Debug.Assert(lengthInChunk >= 0, "Index isn't in the chunk.");
int lengthToCopy = Math.Min(lengthInChunk, count);
ThreadSafeCopy(value, chunk.m_ChunkChars, indexInChunk, lengthToCopy);
// Advance the index.
indexInChunk += lengthToCopy;
if (indexInChunk >= chunk.m_ChunkLength)
{
chunk = Next(chunk);
indexInChunk = 0;
}
count -= lengthToCopy;
if (count == 0)
{
break;
}
value += lengthToCopy;
}
}
}
///
/// This method prevents out-of-bounds writes in the case a different thread updates a field in the builder just before a copy begins.
/// All interesting variables are copied out of the heap into the parameters of this method, and then bounds checks are run.
///
private static unsafe void ThreadSafeCopy(char* sourcePtr, char[] destination, int destinationIndex, int count)
{
if (count > 0)
{
if ((uint)destinationIndex <= (uint)destination.Length && (destinationIndex + count) <= destination.Length)
{
fixed (char* destinationPtr = &destination[destinationIndex])
string.wstrcpy(destinationPtr, sourcePtr, count);
}
else
{
throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.ArgumentOutOfRange_Index);
}
}
}
private static unsafe void ThreadSafeCopy(char[] source, int sourceIndex, Span destination, int destinationIndex, int count)
{
if (count > 0)
{
if ((uint)sourceIndex > (uint)source.Length || count > source.Length - sourceIndex)
{
throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_Index);
}
if ((uint)destinationIndex > (uint)destination.Length || count > destination.Length - destinationIndex)
{
throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.ArgumentOutOfRange_Index);
}
fixed (char* sourcePtr = &source[sourceIndex])
fixed (char* destinationPtr = &MemoryMarshal.GetReference(destination))
string.wstrcpy(destinationPtr + destinationIndex, sourcePtr, count);
}
}
///
/// Gets the chunk corresponding to the logical index in this builder.
///
/// The logical index in this builder.
///
/// After calling this method, you can obtain the actual index within the chunk by
/// subtracting from .
///
private StringBuilder FindChunkForIndex(int index)
{
Debug.Assert(0 <= index && index <= Length);
StringBuilder result = this;
while (result.m_ChunkOffset > index)
{
result = result.m_ChunkPrevious;
}
Debug.Assert(result != null);
return result;
}
///
/// Gets the chunk corresponding to the logical byte index in this builder.
///
/// The logical byte index in this builder.
private StringBuilder FindChunkForByte(int byteIndex)
{
Debug.Assert(0 <= byteIndex && byteIndex <= Length * sizeof(char));
StringBuilder result = this;
while (result.m_ChunkOffset * sizeof(char) > byteIndex)
{
result = result.m_ChunkPrevious;
}
Debug.Assert(result != null);
return result;
}
/// Gets a span representing the remaining space available in the current chunk.
private Span RemainingCurrentChunk
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get => new Span(m_ChunkChars, m_ChunkLength, m_ChunkChars.Length - m_ChunkLength);
}
///
/// Finds the chunk that logically succeeds the specified chunk.
///
/// The chunk whose successor should be found.
///
/// Each chunk only stores the pointer to its logical predecessor, so this routine has to start
/// from the 'this' pointer (which is assumed to represent the whole StringBuilder) and work its
/// way down until it finds the specified chunk (which is O(n)). Thus, it is more expensive than
/// a field fetch.
///
private StringBuilder Next(StringBuilder chunk) => chunk == this ? null : FindChunkForIndex(chunk.m_ChunkOffset + chunk.m_ChunkLength);
///
/// Transfers the character buffer from this chunk to a new chunk, and allocates a new buffer with a minimum size for this chunk.
///
/// The minimum size of the new buffer to be allocated for this chunk.
///
/// This method requires that the current chunk is full. Otherwise, there's no point in shifting the characters over.
/// It also assumes that 'this' is the last chunk in the linked list.
///
private void ExpandByABlock(int minBlockCharCount)
{
Debug.Assert(Capacity == Length, nameof(ExpandByABlock) + " should only be called when there is no space left.");
Debug.Assert(minBlockCharCount > 0);
AssertInvariants();
if ((minBlockCharCount + Length) > m_MaxCapacity || minBlockCharCount + Length < minBlockCharCount)
{
throw new ArgumentOutOfRangeException("requiredLength", SR.ArgumentOutOfRange_SmallCapacity);
}
// - We always need to make the new chunk at least as big as was requested (`minBlockCharCount`).
// - We'd also prefer to make it at least at big as the current length (thus doubling capacity).
// - But this is only up to a maximum, so we stay in the small object heap, and never allocate
// really big chunks even if the string gets really big.
int newBlockLength = Math.Max(minBlockCharCount, Math.Min(Length, MaxChunkSize));
// Check for integer overflow (logical buffer size > int.MaxValue)
if (m_ChunkOffset + m_ChunkLength + newBlockLength < newBlockLength)
throw new OutOfMemoryException();
// Allocate the array before updating any state to avoid leaving inconsistent state behind in case of out of memory exception
char[] chunkChars = new char[newBlockLength];
// Move all of the data from this chunk to a new one, via a few O(1) pointer adjustments.
// Then, have this chunk point to the new one as its predecessor.
m_ChunkPrevious = new StringBuilder(this);
m_ChunkOffset += m_ChunkLength;
m_ChunkLength = 0;
m_ChunkChars = chunkChars;
AssertInvariants();
}
///
/// Creates a new chunk with fields copied from an existing chunk.
///
/// The chunk from which to copy fields.
///
///
/// This method runs in O(1) time. It does not copy data within the character buffer
/// holds, but copies the reference to the character buffer itself
/// (plus a few other fields).
///
///
/// Callers are expected to update subsequently to point to this
/// chunk as its predecessor.
///
///
private StringBuilder(StringBuilder from)
{
m_ChunkLength = from.m_ChunkLength;
m_ChunkOffset = from.m_ChunkOffset;
m_ChunkChars = from.m_ChunkChars;
m_ChunkPrevious = from.m_ChunkPrevious;
m_MaxCapacity = from.m_MaxCapacity;
AssertInvariants();
}
///
/// Creates a gap at a logical index with the specified count.
///
/// The logical index in this builder.
/// The number of characters in the gap.
/// Receives the chunk containing the gap.
/// The index in that points to the gap.
///
/// - If true, then room must be made by inserting a chunk before the current chunk.
/// - If false, then room can be made by shifting characters ahead of
/// in this block forward by provided the characters will still fit in
/// the current chunk after being shifted.
/// - Providing false does not make a difference most of the time, but it can matter when someone
/// inserts lots of small strings at a position in the buffer.
///
///
///
/// Since chunks do not contain references to their successors, it is not always possible for us to make room
/// by inserting space after in case this chunk runs out of space. Thus, we make room
/// by inserting space before the specified index, and having logical indices refer to new locations by the end
/// of this method.
///
///
/// can be used in conjunction with this method to fill in the newly created gap.
///
///
private void MakeRoom(int index, int count, out StringBuilder chunk, out int indexInChunk, bool doNotMoveFollowingChars)
{
AssertInvariants();
Debug.Assert(count > 0);
Debug.Assert(index >= 0);
if (count + Length > m_MaxCapacity || count + Length < count)
{
throw new ArgumentOutOfRangeException("requiredLength", SR.ArgumentOutOfRange_SmallCapacity);
}
chunk = this;
while (chunk.m_ChunkOffset > index)
{
chunk.m_ChunkOffset += count;
chunk = chunk.m_ChunkPrevious;
}
indexInChunk = index - chunk.m_ChunkOffset;
// 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.
// This typically happens when someone repeatedly inserts small strings at a spot (usually the absolute front) of the buffer.
if (!doNotMoveFollowingChars && chunk.m_ChunkLength <= DefaultCapacity * 2 && chunk.m_ChunkChars.Length - chunk.m_ChunkLength >= count)
{
for (int i = chunk.m_ChunkLength; i > indexInChunk; )
{
--i;
chunk.m_ChunkChars[i + count] = chunk.m_ChunkChars[i];
}
chunk.m_ChunkLength += count;
return;
}
// Allocate space for the new chunk, which will go before the current one.
StringBuilder newChunk = new StringBuilder(Math.Max(count, DefaultCapacity), chunk.m_MaxCapacity, chunk.m_ChunkPrevious);
newChunk.m_ChunkLength = count;
// Copy the head of the current buffer to the new buffer.
int copyCount1 = Math.Min(count, indexInChunk);
if (copyCount1 > 0)
{
unsafe
{
fixed (char* chunkCharsPtr = &chunk.m_ChunkChars[0])
{
ThreadSafeCopy(chunkCharsPtr, newChunk.m_ChunkChars, 0, copyCount1);
// Slide characters over in the current buffer to make room.
int copyCount2 = indexInChunk - copyCount1;
if (copyCount2 >= 0)
{
ThreadSafeCopy(chunkCharsPtr + copyCount1, chunk.m_ChunkChars, 0, copyCount2);
indexInChunk = copyCount2;
}
}
}
}
// Wire in the new chunk.
chunk.m_ChunkPrevious = newChunk;
chunk.m_ChunkOffset += count;
if (copyCount1 < count)
{
chunk = newChunk;
indexInChunk = copyCount1;
}
AssertInvariants();
}
///
/// Used by to allocate another chunk.
///
/// The size of the character buffer for this chunk.
/// The maximum capacity, to be stored in this chunk.
/// The predecessor of this chunk.
private StringBuilder(int size, int maxCapacity, StringBuilder previousBlock)
{
Debug.Assert(size > 0);
Debug.Assert(maxCapacity > 0);
m_ChunkChars = new char[size];
m_MaxCapacity = maxCapacity;
m_ChunkPrevious = previousBlock;
if (previousBlock != null)
{
m_ChunkOffset = previousBlock.m_ChunkOffset + previousBlock.m_ChunkLength;
}
AssertInvariants();
}
///
/// Removes a specified number of characters beginning at a logical index in this builder.
///
/// The logical index in this builder to start removing characters.
/// The number of characters to remove.
/// Receives the new chunk containing the logical index.
///
/// Receives the new index in that is associated with the logical index.
///
private void Remove(int startIndex, int count, out StringBuilder chunk, out int indexInChunk)
{
AssertInvariants();
Debug.Assert(startIndex >= 0 && startIndex < Length);
int endIndex = startIndex + count;
// Find the chunks for the start and end of the block to delete.
chunk = this;
StringBuilder endChunk = null;
int endIndexInChunk = 0;
for (;;)
{
if (endIndex - chunk.m_ChunkOffset >= 0)
{
if (endChunk == null)
{
endChunk = chunk;
endIndexInChunk = endIndex - endChunk.m_ChunkOffset;
}
if (startIndex - chunk.m_ChunkOffset >= 0)
{
indexInChunk = startIndex - chunk.m_ChunkOffset;
break;
}
}
else
{
chunk.m_ChunkOffset -= count;
}
chunk = chunk.m_ChunkPrevious;
}
Debug.Assert(chunk != null, "We fell off the beginning of the string!");
int copyTargetIndexInChunk = indexInChunk;
int copyCount = endChunk.m_ChunkLength - endIndexInChunk;
if (endChunk != chunk)
{
copyTargetIndexInChunk = 0;
// Remove the characters after `startIndex` to the end of the chunk.
chunk.m_ChunkLength = indexInChunk;
// Remove the characters in chunks between the start and the end chunk.
endChunk.m_ChunkPrevious = chunk;
endChunk.m_ChunkOffset = chunk.m_ChunkOffset + chunk.m_ChunkLength;
// If the start is 0, then we can throw away the whole start chunk.
if (indexInChunk == 0)
{
endChunk.m_ChunkPrevious = chunk.m_ChunkPrevious;
chunk = endChunk;
}
}
endChunk.m_ChunkLength -= (endIndexInChunk - copyTargetIndexInChunk);
// SafeCritical: We ensure that `endIndexInChunk + copyCount` is within range of `m_ChunkChars`, and
// also ensure that `copyTargetIndexInChunk + copyCount` is within the chunk.
// Remove any characters in the end chunk, by sliding the characters down.
if (copyTargetIndexInChunk != endIndexInChunk) // Sometimes no move is necessary
{
ThreadSafeCopy(endChunk.m_ChunkChars, endIndexInChunk, endChunk.m_ChunkChars, copyTargetIndexInChunk, copyCount);
}
Debug.Assert(chunk != null, "We fell off the beginning of the string!");
AssertInvariants();
}
}
}