// 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.Versioning; using System.Security; using System.Threading; using System.Globalization; using System.Diagnostics; using System.Diagnostics.Contracts; 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. // // When passing null into a constructor in VJ and VC, the null // should be explicitly type cast. // For Example: // StringBuilder sb1 = new StringBuilder((StringBuilder)null); // StringBuilder sb2 = new StringBuilder((String)null); // Console.WriteLine(sb1); // Console.WriteLine(sb2); // [Serializable] 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. // // // CLASS VARIABLES // // internal char[] m_ChunkChars; // The characters in this block internal StringBuilder m_ChunkPrevious; // Link to the block logically before this block internal int m_ChunkLength; // The index in m_ChunkChars that represent the end of the block internal int m_ChunkOffset; // The logical offset (sum of all characters in previous blocks) internal int m_MaxCapacity = 0; // // // STATIC CONSTANTS // // internal const int DefaultCapacity = 16; private const String CapacityField = "Capacity"; private const String MaxCapacityField = "m_MaxCapacity"; private const String StringValueField = "m_StringValue"; private const String ThreadIDField = "m_currentThread"; // 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; // // //CONSTRUCTORS // // // Creates a new empty string builder (i.e., it represents String.Empty) // with the default capacity (16 characters). public StringBuilder() { m_MaxCapacity = int.MaxValue; m_ChunkChars = new char[DefaultCapacity]; } // Create a new empty string builder (i.e., it represents String.Empty) // with the specified capacity. public StringBuilder(int capacity) : this(capacity, int.MaxValue) { } // Creates a new string builder from the specified string. If value // is a null String (i.e., if it represents String.NullString) // then the new string builder will also be null (i.e., it will also represent // String.NullString). // public StringBuilder(String value) : this(value, DefaultCapacity) { } // Creates a new string builder from the specified string with the specified // capacity. If value is a null String (i.e., if it represents // String.NullString) then the new string builder will also be null // (i.e., it will also represent String.NullString). // The maximum number of characters this string may contain is set by capacity. // public StringBuilder(String value, int capacity) : this(value, 0, ((value != null) ? value.Length : 0), capacity) { } // Creates a new string builder from the specifed substring with the specified // capacity. The maximum number of characters is set by capacity. // 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); } Contract.EndContractBlock(); if (value == null) { value = String.Empty; } if (startIndex > value.Length - length) { throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_IndexLength); } m_MaxCapacity = Int32.MaxValue; if (capacity == 0) { capacity = DefaultCapacity; } if (capacity < length) capacity = length; m_ChunkChars = new char[capacity]; m_ChunkLength = length; unsafe { fixed (char* sourcePtr = value) ThreadSafeCopy(sourcePtr + startIndex, m_ChunkChars, 0, length); } } // Creates an empty StringBuilder with a minimum capacity of capacity // and a maximum capacity of maxCapacity. 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))); } Contract.EndContractBlock(); 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)); Contract.EndContractBlock(); int persistedCapacity = 0; string persistedString = null; int persistedMaxCapacity = Int32.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 forward 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 = DefaultCapacity; if (persistedCapacity < persistedString.Length) { persistedCapacity = persistedString.Length; } if (persistedCapacity > persistedMaxCapacity) { persistedCapacity = 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; VerifyClassInvariant(); } void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) { if (info == null) { throw new ArgumentNullException(nameof(info)); } Contract.EndContractBlock(); VerifyClassInvariant(); 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 VerifyClassInvariant() { Debug.Assert((uint)(m_ChunkOffset + m_ChunkChars.Length) >= m_ChunkOffset, "Integer Overflow"); StringBuilder currentBlock = this; int maxCapacity = this.m_MaxCapacity; for (;;) { // All blocks have copy of the maxCapacity. Debug.Assert(currentBlock.m_MaxCapacity == maxCapacity, "Bad maxCapacity"); Debug.Assert(currentBlock.m_ChunkChars != null, "Empty Buffer"); Debug.Assert(currentBlock.m_ChunkLength <= currentBlock.m_ChunkChars.Length, "Out of range length"); Debug.Assert(currentBlock.m_ChunkLength >= 0, "Negative length"); Debug.Assert(currentBlock.m_ChunkOffset >= 0, "Negative offset"); StringBuilder prevBlock = currentBlock.m_ChunkPrevious; if (prevBlock == null) { Debug.Assert(currentBlock.m_ChunkOffset == 0, "First chunk's offset is not 0"); break; } // There are no gaps in the blocks. Debug.Assert(currentBlock.m_ChunkOffset == prevBlock.m_ChunkOffset + prevBlock.m_ChunkLength, "There is a gap between chunks!"); 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); } Contract.EndContractBlock(); 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; } } } public int MaxCapacity { get { return m_MaxCapacity; } } // Ensures that the capacity of this string builder is at least the specified value. // If capacity is greater than the capacity of this string builder, then the capacity // is set to capacity; otherwise the capacity is unchanged. // public int EnsureCapacity(int capacity) { if (capacity < 0) { throw new ArgumentOutOfRangeException(nameof(capacity), SR.ArgumentOutOfRange_NegativeCapacity); } Contract.EndContractBlock(); if (Capacity < capacity) Capacity = capacity; return Capacity; } public override String ToString() { Contract.Ensures(Contract.Result() != null); VerifyClassInvariant(); if (Length == 0) return String.Empty; string ret = string.FastAllocateString(Length); StringBuilder chunk = this; unsafe { fixed (char* destinationPtr = ret) { 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)ret.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 ret; } } } // Converts a substring of this string builder to a String. public String ToString(int startIndex, int length) { Contract.Ensures(Contract.Result() != null); 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); } VerifyClassInvariant(); StringBuilder chunk = this; int sourceEndIndex = startIndex + length; string ret = string.FastAllocateString(length); int curDestIndex = length; unsafe { fixed (char* destinationPtr = ret) { while (curDestIndex > 0) { int chunkEndIndex = sourceEndIndex - chunk.m_ChunkOffset; if (chunkEndIndex >= 0) { if (chunkEndIndex > chunk.m_ChunkLength) chunkEndIndex = chunk.m_ChunkLength; int countLeft = curDestIndex; int chunkCount = countLeft; int chunkStartIndex = chunkEndIndex - countLeft; if (chunkStartIndex < 0) { chunkCount += chunkStartIndex; chunkStartIndex = 0; } curDestIndex -= chunkCount; if (chunkCount > 0) { // work off of local variables so that they are stable even in the presence of race conditions char[] sourceArray = chunk.m_ChunkChars; // Check that we will not overrun our boundaries. if ((uint)(chunkCount + curDestIndex) <= (uint)length && (uint)(chunkCount + chunkStartIndex) <= (uint)sourceArray.Length) { fixed (char* sourcePtr = &sourceArray[chunkStartIndex]) string.wstrcpy(destinationPtr + curDestIndex, sourcePtr, chunkCount); } else { throw new ArgumentOutOfRangeException(nameof(chunkCount), SR.ArgumentOutOfRange_Index); } } } chunk = chunk.m_ChunkPrevious; } return ret; } } } // Convenience method for sb.Length=0; public StringBuilder Clear() { this.Length = 0; return this; } // Sets the length of the String in this buffer. If length is less than the current // instance, the StringBuilder is truncated. If length is greater than the current // instance, nulls are appended. The capacity is adjusted to be the same as the length. public int Length { get { Contract.Ensures(Contract.Result() >= 0); 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); } Contract.EndContractBlock(); int originalCapacity = Capacity; if (value == 0 && m_ChunkPrevious == null) { m_ChunkLength = 0; m_ChunkOffset = 0; Debug.Assert(Capacity >= originalCapacity, "setting the Length should never decrease the Capacity"); return; } int delta = value - Length; // if the specified length is greater than the current length if (delta > 0) { // the end of the string value of the current StringBuilder object is padded with the Unicode NULL character Append('\0', delta); // We could improve on this, but who does this anyway? } // if the specified length is less than or equal to the current length else { StringBuilder chunk = FindChunkForIndex(value); if (chunk != this) { // we crossed a chunk boundary when reducing the Length, we must replace this middle-chunk with a new // larger chunk to ensure the original capacity is preserved int newLen = originalCapacity - chunk.m_ChunkOffset; char[] newArray = new char[newLen]; Debug.Assert(newLen > chunk.m_ChunkChars.Length, "the new chunk should be larger than the one it is replacing"); Array.Copy(chunk.m_ChunkChars, 0, newArray, 0, chunk.m_ChunkLength); m_ChunkChars = newArray; m_ChunkPrevious = chunk.m_ChunkPrevious; m_ChunkOffset = chunk.m_ChunkOffset; } m_ChunkLength = value - chunk.m_ChunkOffset; VerifyClassInvariant(); } Debug.Assert(Capacity >= originalCapacity, "setting the Length should never decrease the Capacity"); } } [System.Runtime.CompilerServices.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); } } } // Appends a character at the end of this string builder. The capacity is adjusted as needed. public StringBuilder Append(char value, int repeatCount) { if (repeatCount < 0) { throw new ArgumentOutOfRangeException(nameof(repeatCount), SR.ArgumentOutOfRange_NegativeCount); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); 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 idx = m_ChunkLength; while (repeatCount > 0) { if (idx < m_ChunkChars.Length) { m_ChunkChars[idx++] = value; --repeatCount; } else { m_ChunkLength = idx; ExpandByABlock(repeatCount); Debug.Assert(m_ChunkLength == 0, "Expand should create a new block"); idx = 0; } } m_ChunkLength = idx; VerifyClassInvariant(); return this; } // Appends an array of characters at the end of this string builder. The capacity is adjusted as needed. 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); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); 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 copy of this string at the end of this string builder. public StringBuilder Append(String value) { Contract.Ensures(Contract.Result() != null); if (value != null) { // This is a hand specialization of the 'AppendHelper' code below. // We could have just called AppendHelper. char[] chunkChars = m_ChunkChars; int chunkLength = m_ChunkLength; int valueLen = value.Length; int newCurrentIndex = chunkLength + valueLen; if (newCurrentIndex < chunkChars.Length) // Use strictly < to avoid issue 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 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 a copy of the characters in value from startIndex to startIndex + // count at the end of this string builder. 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); } Contract.Ensures(Contract.Result() != null); //If the value being added is null, eat the null //and return. 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 AppendLine() { Contract.Ensures(Contract.Result() != null); return Append(Environment.NewLine); } public StringBuilder AppendLine(string value) { Contract.Ensures(Contract.Result() != null); 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 (count < 0) { throw new ArgumentOutOfRangeException(nameof(count), SR.Arg_NegativeArgCount); } 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); } if ((uint)sourceIndex > (uint)Length) { throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_Index); } if (sourceIndex > Length - count) { throw new ArgumentException(SR.Arg_LongerThanSrcString); } Contract.EndContractBlock(); VerifyClassInvariant(); StringBuilder chunk = this; int sourceEndIndex = sourceIndex + count; int curDestIndex = destinationIndex + count; while (count > 0) { int chunkEndIndex = sourceEndIndex - chunk.m_ChunkOffset; if (chunkEndIndex >= 0) { if (chunkEndIndex > chunk.m_ChunkLength) chunkEndIndex = chunk.m_ChunkLength; int chunkCount = count; int chunkStartIndex = chunkEndIndex - count; if (chunkStartIndex < 0) { chunkCount += chunkStartIndex; chunkStartIndex = 0; } curDestIndex -= chunkCount; count -= chunkCount; // SafeCritical: 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 multiple copies of a string into this string builder at the specified position. // Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, this // string builder is not changed. // public StringBuilder Insert(int index, String value, int count) { if (count < 0) { throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_NeedNonNegNum); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); //Range check the index. int currentLength = Length; if ((uint)index > (uint)currentLength) { throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index); } //If value is null, empty or count is 0, do nothing. This is ECMA standard. if (value == null || value.Length == 0 || 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 inserted characters. long insertingChars = (long)value.Length * count; if (insertingChars > MaxCapacity - this.Length) { throw new OutOfMemoryException(); } Debug.Assert(insertingChars + this.Length < Int32.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 the specified characters from this string builder. // The length of this string builder is reduced by // length, but the capacity is unaffected. // 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); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); if (Length == length && startIndex == 0) { // Optimization. If we are deleting everything Length = 0; return this; } if (length > 0) { StringBuilder chunk; int indexInChunk; Remove(startIndex, length, out chunk, out indexInChunk); } return this; } // Appends a boolean to the end of this string builder. // The capacity is adjusted as needed. public StringBuilder Append(bool value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends an sbyte to this string builder. // The capacity is adjusted as needed. [CLSCompliant(false)] public StringBuilder Append(sbyte value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends a ubyte to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(byte value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends a character at the end of this string builder. The capacity is adjusted as needed. public StringBuilder Append(char value) { Contract.Ensures(Contract.Result() != null); if (m_ChunkLength < m_ChunkChars.Length) m_ChunkChars[m_ChunkLength++] = value; else Append(value, 1); return this; } // Appends a short to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(short value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends an int to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(int value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends a long to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(long value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends a float to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(float value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends a double to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(double value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } public StringBuilder Append(decimal value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends an ushort to this string builder. // The capacity is adjusted as needed. [CLSCompliant(false)] public StringBuilder Append(ushort value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends an uint to this string builder. // The capacity is adjusted as needed. [CLSCompliant(false)] public StringBuilder Append(uint value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends an unsigned long to this string builder. // The capacity is adjusted as needed. [CLSCompliant(false)] public StringBuilder Append(ulong value) { Contract.Ensures(Contract.Result() != null); return Append(value.ToString()); } // Appends an Object to this string builder. // The capacity is adjusted as needed. public StringBuilder Append(Object value) { Contract.Ensures(Contract.Result() != null); if (null == value) { //Appending null is now a no-op. return this; } return Append(value.ToString()); } // Appends all of the characters in value to the current instance. public StringBuilder Append(char[] value) { Contract.Ensures(Contract.Result() != null); if (null != value && value.Length > 0) { unsafe { fixed (char* valueChars = &value[0]) Append(valueChars, value.Length); } } return this; } #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) { if (values == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.values); using (var 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 (var i = 1; i < values.Length; i++) { Append(separator, separatorLength); if (values[i] != null) Append(values[i].ToString()); } return this; } #endregion /*====================================Insert==================================== ** ==============================================================================*/ // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, String value) { if ((uint)index > (uint)Length) { throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); if (value != null) { unsafe { fixed (char* sourcePtr = value) Insert(index, sourcePtr, value.Length); } } return this; } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, bool value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // [CLSCompliant(false)] public StringBuilder Insert(int index, sbyte value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, byte value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, short value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. public StringBuilder Insert(int index, char value) { Contract.Ensures(Contract.Result() != null); unsafe { Insert(index, &value, 1); } return this; } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, char[] value) { if ((uint)index > (uint)Length) { throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); if (value != null) Insert(index, value, 0, value.Length); return this; } // Returns a reference to the StringBuilder with charCount characters from // value inserted into the buffer at index. Existing characters are shifted // to make room for the new text and capacity is adjusted as required. If value is null, the StringBuilder // is unchanged. Characters are taken from value starting at position startIndex. public StringBuilder Insert(int index, char[] value, int startIndex, int charCount) { Contract.Ensures(Contract.Result() != null); int currentLength = Length; if ((uint)index > (uint)currentLength) { throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_Index); } //If they passed in a null char array, just jump out quickly. if (value == null) { if (startIndex == 0 && charCount == 0) { return this; } throw new ArgumentNullException(nameof(value), SR.ArgumentNull_String); } //Range check the array. 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; } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, int value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, long value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, float value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with ; value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. // public StringBuilder Insert(int index, double value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } public StringBuilder Insert(int index, decimal value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. // [CLSCompliant(false)] public StringBuilder Insert(int index, ushort value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. // [CLSCompliant(false)] public StringBuilder Insert(int index, uint value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to the StringBuilder with value inserted into // the buffer at index. Existing characters are shifted to make room for the new text. // The capacity is adjusted as needed. // [CLSCompliant(false)] public StringBuilder Insert(int index, ulong value) { Contract.Ensures(Contract.Result() != null); return Insert(index, value.ToString(), 1); } // Returns a reference to this string builder with value inserted into // the buffer at index. Existing characters are shifted to make room for the // new text. The capacity is adjusted as needed. If value equals String.Empty, the // StringBuilder is not changed. No changes are made if value is null. // public StringBuilder Insert(int index, Object value) { Contract.Ensures(Contract.Result() != null); if (null == value) { return this; } return Insert(index, value.ToString(), 1); } public StringBuilder AppendFormat(String format, Object arg0) { Contract.Ensures(Contract.Result() != null); return AppendFormatHelper(null, format, new ParamsArray(arg0)); } public StringBuilder AppendFormat(String format, Object arg0, Object arg1) { Contract.Ensures(Contract.Result() != null); return AppendFormatHelper(null, format, new ParamsArray(arg0, arg1)); } public StringBuilder AppendFormat(String format, Object arg0, Object arg1, Object arg2) { Contract.Ensures(Contract.Result() != null); return 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. throw new ArgumentNullException((format == null) ? nameof(format) : nameof(args)); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); return AppendFormatHelper(null, format, new ParamsArray(args)); } public StringBuilder AppendFormat(IFormatProvider provider, String format, Object arg0) { Contract.Ensures(Contract.Result() != null); return AppendFormatHelper(provider, format, new ParamsArray(arg0)); } public StringBuilder AppendFormat(IFormatProvider provider, String format, Object arg0, Object arg1) { Contract.Ensures(Contract.Result() != null); return AppendFormatHelper(provider, format, new ParamsArray(arg0, arg1)); } public StringBuilder AppendFormat(IFormatProvider provider, String format, Object arg0, Object arg1, Object arg2) { Contract.Ensures(Contract.Result() != null); return 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. throw new ArgumentNullException((format == null) ? nameof(format) : nameof(args)); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); 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 Index_Limit = 1000000; // Note: 0 <= ArgIndex < Index_Limit private const int Width_Limit = 1000000; // Note: -Width_Limit < ArgAlign < Width_Limit internal StringBuilder AppendFormatHelper(IFormatProvider provider, String format, ParamsArray args) { if (format == null) { throw new ArgumentNullException(nameof(format)); } Contract.Ensures(Contract.Result() != null); Contract.EndContractBlock(); 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 < Index_Limit); // 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 < Width_Limit); // 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; // 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 itemFormat = format.Substring(startPos, pos - startPos); } } else { unescapedItemFormat.Append(format, startPos, pos - startPos); 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) { s = cf.Format(itemFormat, arg, provider); } if (s == null) { IFormattable formattableArg = arg as IFormattable; if (formattableArg != null) { 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; } // Returns a reference to the current StringBuilder with all instances of oldString // replaced with newString. If startIndex and count are specified, // we only replace strings completely contained in the range of startIndex to startIndex + // count. The strings to be replaced are checked on an ordinal basis (e.g. not culture aware). If // newValue is null, instances of oldValue are removed (e.g. replaced with nothing.). // public StringBuilder Replace(String oldValue, String newValue) { Contract.Ensures(Contract.Result() != null); return Replace(oldValue, newValue, 0, Length); } public bool Equals(StringBuilder sb) { if (sb == null) return false; if (Capacity != sb.Capacity || MaxCapacity != sb.MaxCapacity || 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 (;;) { // Decrement the pointer to the 'this' StringBuilder --thisChunkIndex; --sbChunkIndex; while (thisChunkIndex < 0) { thisChunk = thisChunk.m_ChunkPrevious; if (thisChunk == null) break; thisChunkIndex = thisChunk.m_ChunkLength + thisChunkIndex; } // Decrement the pointer to the 'this' StringBuilder 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; } } public StringBuilder Replace(String oldValue, String newValue, int startIndex, int count) { Contract.Ensures(Contract.Result() != null); 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)); } if (newValue == null) newValue = ""; 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 my 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 beginning } 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 logical index and back afterward. 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"); } } VerifyClassInvariant(); return this; } // Returns a StringBuilder with all instances of oldChar replaced with // newChar. The size of the StringBuilder is unchanged because we're only // replacing characters. If startIndex and count are specified, we // only replace characters in the range from startIndex to startIndex+count // public StringBuilder Replace(char oldChar, char newChar) { return Replace(oldChar, newChar, 0, Length); } public StringBuilder Replace(char oldChar, char newChar, int startIndex, int count) { Contract.Ensures(Contract.Result() != null); 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; } return this; } /// /// Appends 'value' of length 'count' to the stringBuilder. /// [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, "Expand did not make a new block"); // Copy the second chunk ThreadSafeCopy(value + firstLength, m_ChunkChars, 0, restLength); m_ChunkLength = restLength; } VerifyClassInvariant(); return this; } /// /// Inserts 'value' of length 'cou /// unsafe private 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); } } /// /// 'replacements' is a list of index (relative to the begining of the 'chunk' to remove /// 'removeCount' characters and replace them with 'value'. This routine does all those /// replacements in bulk (and therefore very efficiently. /// with the string 'value'. /// 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. int delta = (value.Length - removeCount) * replacementsCount; 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 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 true if the string that is starts at 'chunk' and 'indexInChunk, and has a logical /// length of 'count' starts with the string 'value'. /// 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; } // See if there no match, break out of the inner for loop if (value[i] != chunk.m_ChunkChars[indexInChunk]) return false; indexInChunk++; --count; } return true; } /// /// ReplaceInPlaceAtChunk is the logical equivalent of 'memcpy'. Given a chunk and ann index in /// that chunk, it copies in 'count' characters from 'value' and updates 'chunk, and indexInChunk to /// point at the end of the characters just copyied (thus you can splice in strings from multiple /// places by calling this mulitple times. /// unsafe private 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 not in 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; } } } /// /// We have to prevent modification off the end of an array. /// The only way to do this is to copy all interesting variables out of the heap and then do the /// bounds check. This is what we do here. /// 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 void ThreadSafeCopy(char[] source, int sourceIndex, char[] destination, int destinationIndex, int count) { if (count > 0) { if ((uint)sourceIndex <= (uint)source.Length && (sourceIndex + count) <= source.Length) { unsafe { fixed (char* sourcePtr = &source[sourceIndex]) ThreadSafeCopy(sourcePtr, destination, destinationIndex, count); } } else { throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_Index); } } } /// /// Finds the chunk for the logical index (number of characters in the whole stringbuilder) 'index' /// YOu can then get the offset in this chunk by subtracting the m_BlockOffset field from 'index' /// /// /// private StringBuilder FindChunkForIndex(int index) { Debug.Assert(0 <= index && index <= Length, "index not in string"); StringBuilder ret = this; while (ret.m_ChunkOffset > index) ret = ret.m_ChunkPrevious; Debug.Assert(ret != null, "index not in string"); return ret; } /// /// Finds the chunk for the logical byte index 'byteIndex' /// /// /// private StringBuilder FindChunkForByte(int byteIndex) { Debug.Assert(0 <= byteIndex && byteIndex <= Length * sizeof(char), "Byte Index not in string"); StringBuilder ret = this; while (ret.m_ChunkOffset * sizeof(char) > byteIndex) ret = ret.m_ChunkPrevious; Debug.Assert(ret != null, "Byte Index not in string"); return ret; } /// /// Finds the chunk that logically follows the 'chunk' chunk. Chunks only persist the pointer to /// the chunk that is logically before it, so this routine has to start at the this pointer (which /// is a assumed to point at the chunk representing the whole stringbuilder) and search /// until it finds the current chunk (thus is O(n)). So it is more expensive than a field fetch! /// private StringBuilder Next(StringBuilder chunk) { if (chunk == this) return null; return FindChunkForIndex(chunk.m_ChunkOffset + chunk.m_ChunkLength); } /// /// Assumes that 'this' is the last chunk in the list and that it is full. Upon return the 'this' /// block is updated so that it is a new block that has at least 'minBlockCharCount' characters. /// that can be used to copy characters into it. /// private void ExpandByABlock(int minBlockCharCount) { Contract.Requires(Capacity == Length, "Expand expect to be called only when there is no space left"); // We are currently full Contract.Requires(minBlockCharCount > 0, "Expansion request must be positive"); VerifyClassInvariant(); if ((minBlockCharCount + Length) > m_MaxCapacity || minBlockCharCount + Length < minBlockCharCount) throw new ArgumentOutOfRangeException("requiredLength", SR.ArgumentOutOfRange_SmallCapacity); // Compute the length of the new block we need // We make the new chunk at least big enough for the current need (minBlockCharCount) // But also as big as the current length (thus doubling capacity), 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)); // Copy the current block to the new block, and initialize this to point at the new buffer. m_ChunkPrevious = new StringBuilder(this); m_ChunkOffset += m_ChunkLength; m_ChunkLength = 0; // Check for integer overflow (logical buffer size > int.MaxInt) if (m_ChunkOffset + newBlockLength < newBlockLength) { m_ChunkChars = null; throw new OutOfMemoryException(); } m_ChunkChars = new char[newBlockLength]; VerifyClassInvariant(); } /// /// Used by ExpandByABlock to create a new chunk. The new chunk is a copied from 'from' /// In particular the buffer is shared. It is expected that 'from' chunk (which represents /// the whole list, is then updated to point to point to this new chunk. /// 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; VerifyClassInvariant(); } /// /// Creates a gap of size 'count' at the logical offset (count of characters in the whole string /// builder) 'index'. It returns the 'chunk' and 'indexInChunk' which represents a pointer to /// this gap that was just created. You can then use 'ReplaceInPlaceAtChunk' to fill in the /// chunk /// /// ReplaceAllChunks relies on the fact that indexes above 'index' are NOT moved outside 'chunk' /// by this process (because we make the space by creating the cap BEFORE the chunk). If we /// change this ReplaceAllChunks needs to be updated. /// /// If dontMoveFollowingChars is true, then the room must be made by inserting a chunk BEFORE the /// current chunk (this is what it does most of the time anyway) /// private void MakeRoom(int index, int count, out StringBuilder chunk, out int indexInChunk, bool doneMoveFollowingChars) { VerifyClassInvariant(); Debug.Assert(count > 0, "Count must be strictly positive"); Debug.Assert(index >= 0, "Index can't be negative"); 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 you don't have to copy much to get it, go ahead // and use it. This happens typically when you repeatedly insert small strings at a spot // (typically the absolute front) of the buffer. if (!doneMoveFollowingChars && 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 (will go before this one) StringBuilder newChunk = new StringBuilder(Math.Max(count, DefaultCapacity), chunk.m_MaxCapacity, chunk.m_ChunkPrevious); newChunk.m_ChunkLength = count; // Copy the head of the 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 in the current buffer over to make room. int copyCount2 = indexInChunk - copyCount1; if (copyCount2 >= 0) { ThreadSafeCopy(chunkCharsPtr + copyCount1, chunk.m_ChunkChars, 0, copyCount2); indexInChunk = copyCount2; } } } } chunk.m_ChunkPrevious = newChunk; // Wire in the new chunk chunk.m_ChunkOffset += count; if (copyCount1 < count) { chunk = newChunk; indexInChunk = copyCount1; } VerifyClassInvariant(); } /// /// Used by MakeRoom to allocate another chunk. /// private StringBuilder(int size, int maxCapacity, StringBuilder previousBlock) { Debug.Assert(size > 0, "size not positive"); Debug.Assert(maxCapacity > 0, "maxCapacity not positive"); m_ChunkChars = new char[size]; m_MaxCapacity = maxCapacity; m_ChunkPrevious = previousBlock; if (previousBlock != null) m_ChunkOffset = previousBlock.m_ChunkOffset + previousBlock.m_ChunkLength; VerifyClassInvariant(); } /// /// Removes 'count' characters from the logical index 'startIndex' and returns the chunk and /// index in the chunk of that logical index in the out parameters. /// private void Remove(int startIndex, int count, out StringBuilder chunk, out int indexInChunk) { VerifyClassInvariant(); Debug.Assert(startIndex >= 0 && startIndex < Length, "startIndex not in string"); 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, "fell off beginning of string!"); int copyTargetIndexInChunk = indexInChunk; int copyCount = endChunk.m_ChunkLength - endIndexInChunk; if (endChunk != chunk) { copyTargetIndexInChunk = 0; // Remove the characters after startIndex to end of the chunk chunk.m_ChunkLength = indexInChunk; // Remove the characters in chunks between start and 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, "fell off beginning of string!"); VerifyClassInvariant(); } } }