ReadOnlySpan<char> Replace extensions

[daveaglick]

It would be useful to have Replace() methods for ReadOnlySpan<char> similar to the ones for string. This was briefly mentioned in #22434 but then the Replace API was removed from the proposal for needing more work. As far as I can tell, it hasn't been revisited yet.

Here's my proposal to get things started:

public static class MemoryExtensions
{
    public static ReadOnlySpan<char> Replace(
        this ReadOnlySpan<char> str,
        ReadOnlySpan<char> oldValue,
        ReadOnlySpan<char> newValue);

    // If buffer is null or too small a new internal one will be created with the correct size and bufferCount = 0, return value is the created buffer
    // If buffer is the correct size it will be filled and bufferCount = buffer.Length (how much was filled), return value is the filled buffer
    // If buffer is too big it will be filled and bufferCount = how much was filled, return value is a slice of the filled buffer
    public static ReadOnlySpan<char> Replace(
        this ReadOnlySpan<char> str,
        ReadOnlySpan<char> oldValue,
        ReadOnlySpan<char> newValue,
        Span<char> buffer,
        out int bytesWritten)
}

I think this covers almost all use cases including those where the user wants to provide their own refillable buffer to reduce allocations. These two APIs have the following features:

• Provides an overload that works almost exactly like the string version.
• The overload that takes a buffer can be used when the user doesn't want the Replace method to allocate an internal buffer.
• If the provided buffer isn't large enough, a new one will be allocated ensuring success. I prefer this over a try pattern where the replace call might fail - I don't think failing string operations is a user-friendly option.
• The bytesWritten value can be checked to see if the provided buffer was used or filled (and by how much) and the caller can act accordingly.

Question: would we also want a public static ReadOnlySpan<char> Replace(this ReadOnlySpan<char> str, char oldChar, char newChar)? If so, that's probably easy enough to implement separately since we don't need to calculate the final buffer size or look ahead to determine matching.

I've been working out a naive implementation alongside the API definition to clarify my thoughts on the API surface. Here's what I've got so far - I include it for reference and as a point of discussion (and also to get any tips on how to further reduce allocations or improve performance, it's not quite as light or fast as the OOTB string.Replace() though I suspect there are still some optimizations to be had):

Expand

public static class SpanExtensions
{
    public static ReadOnlySpan<char> Replace(
    this ReadOnlySpan<char> str,
    ReadOnlySpan<char> oldValue,
    ReadOnlySpan<char> newValue) =>
    Replace(str, oldValue, newValue, null, out int _);

    public static ReadOnlySpan<char> Replace(
        this ReadOnlySpan<char> str,
        ReadOnlySpan<char> oldValue,
        ReadOnlySpan<char> newValue,
        Span<char> buffer,
        out int bytesWritten)
    {
        if (str == null)
        {
            throw new ArgumentNullException(nameof(str));
        }
        if (oldValue == null)
        {
            throw new ArgumentNullException(nameof(oldValue));
        }
        if (oldValue.Length == 0)
        {
            throw new ArgumentException("String cannot be of zero length", nameof(oldValue));
        }

        // When they're both equal just return the original
        bytesWritten = 0;
        if (newValue != null && oldValue.Equals(newValue, StringComparison.Ordinal))
        {
            return str;
        }

        // Get the replacement positions// Figure out the replacement positions
        // Partly lifted from logic in StringBuilder.Replace()
        int[] replacements = null;
        int replacementsCount = 0;
        int strIndex = 0;
        for (int c = 0; c < str.Length; c++)
        {
            if (str[c] == oldValue[strIndex])
            {
                strIndex++;
            }
            if (strIndex == oldValue.Length)
            {
                if (replacements == null)
                {
                    replacements = new int[5];
                }
                else if (replacementsCount > replacements.Length)
                {
                    // From StringBuilder.Replace() - grow by 1.5x but more in the begining
                    int[] newReplacements = new int[replacements.Length * 3 / 2 + 4];
                    Array.Copy(replacements, newReplacements, replacements.Length);
                    replacements = newReplacements;
                }
                replacements[replacementsCount++] = c - strIndex + 1;
                strIndex = 0;
            }
        }

        // Return the original string if no replacements were performed
        if (replacementsCount == 0)
        {
            return str;
        }

        // Size the buffer
        if (buffer == null || buffer.Length < str.Length + ((newValue.Length - oldValue.Length) * replacementsCount))
        {
            // Create a new buffer because the passed in one wasn't the right size
            buffer = new char[str.Length + ((newValue.Length - oldValue.Length) * replacementsCount)];
        }
        else
        {
            // Use the existing buffer and set the count
            bytesWritten = str.Length + ((newValue.Length - oldValue.Length) * replacementsCount);
        }

        // Perform replacements
        strIndex = 0;
        int charsIndex = 0;
        for (int c = 0; c < replacementsCount; c++)
        {
            // Copy up to the next replacement
            while (strIndex < replacements[c])
            {
                buffer[charsIndex++] = str[strIndex++];
            }

            // Perform the replacement (use strIndex to temporarily hold value index)
            strIndex = 0;
            while (strIndex < newValue.Length)
            {
                buffer[charsIndex++] = newValue[strIndex++];
            }
            strIndex = replacements[c] + oldValue.Length;
        }

        // No more replacements, copy the rest of the string
        while (strIndex < str.Length)
        {
            buffer[charsIndex++] = str[strIndex++];
        }

        // Slice the buffer if we didn't use the whole thing
        return charsIndex == bytesWritten ? buffer : buffer.Slice(0, charsIndex);
    }
}

cc @davkean who expressed an interest in this API.

[daveaglick]

Feedback on Twitter seems to be that a TryReplace version should be provided as well (or instead). I’d amend the proposal to include...

public static bool TryReplace(
    this ReadOnlySpan<char> str,
    ReadOnlySpan<char> oldValue,
    ReadOnlySpan<char> newValue,
    Span<char> buffer,
    out int bufferSize)
}

...where bufferSize would always indicate the required number of char regardless of success (so a properly sized buffer could be allocated in a second pass on failure). This overload would not attempt to allocate a new buffer if the provided one is not sufficient.

I do feel like having “just works” versions are important. Not everyone is going to care about allocations or performance and will want to control those - I’m guessing as Span (and particularly ReadOnlySpan<char>) become more popular and common, there will be users who have a string-like span from somewhere else and just want to do string-like operations without actually converting to and from strings.

[daveaglick]

Thought about this some more, here's an updated proposal:

public static class MemoryExtensions
{
    // Allocates a new buffer, fills it, and returns it
    public static ReadOnlySpan<char> Replace(
        this ReadOnlySpan<char> str,
        ReadOnlySpan<char> oldValue,
        ReadOnlySpan<char> newValue);

    // Always returns the required buffer size regardless of success
    public static bool TryReplace(
        this ReadOnlySpan<char> str,
        ReadOnlySpan<char> oldValue,
        ReadOnlySpan<char> newValue,
        Span<char> buffer,
        out int bufferSize);

    // Always returns the required buffer size regardless of success
    public static bool TryReplace(
        this Span<char> str,
        ReadOnlySpan<char> oldValue,
        ReadOnlySpan<char> newValue,
        out int bufferSize);

    // Allocates a new buffer, fills it, and returns it
    public static ReadOnlySpan<char> Replace(
        this ReadOnlySpan<char> str,
        char oldChar,
        char newChar);

    // Don't need to return buffer size since it's it same as input length
    public static bool TryReplace(
        this ReadOnlySpan<char> str,
        char oldChar,
        char newChar
        Span<char> buffer);

    // This will always succeed
    public static void Replace(
        this Span<char> str,
        char oldChar,
        char newChar);
}

• Removed the overload that maybe allocates or maybe fills - on second thought that seems both more confusing and less helpful than I initially thought it would be.
• Added an overload that takes a Span<char> as both the initial input and the buffer to fill (overwriting what was in it).
• Added overloads for char

One other thought/question I had was about what to do when using an overload that fills a provided buffer when either the old value is the same as the new value or no replacements need to be performed. In the overloads where a new buffer is allocated we can just return the original input. In the overloads where we're filling a provided buffer, should the buffer still be filled by copying over the content from the original input verbatim or should we somehow indicate the original input contains the results and no replacement is needed (I.e., return true with a bufferSize of 0 or -1)? My first thought is that filling the buffer regardless is better for consistency, but then we miss out on a not-uncommon optimization (is copying to the buffer really that much of a performance impact?).

[vcsjones]

I like the API idea and agree it's useful, I have some thoughts on the shape though.

Returning spans from a method is generally not something I would use unless the span's creation is guaranteed not to allocate (like if you are returning a slice of a span parameter).

I do feel like having “just works” versions are important. Not everyone is going to care about allocations or performance and will want to control those

In those circumstances I do not think using Span<T> is an appropriate choice and I would suggest using string again. I think if APIs are designed as such to make it seem that string is somehow obsolete, when that is very far from the truth, is problematic. A big-but-not-always use case for Span<T> is to be in control of allocations.

---

Some of these API suggestions like Replace(Span<char> str, char oldChar, char newChar) look like they could be useful if they were generalized over IEquatable<T>. Perhaps then the API could be:

public static void Replace(Span<T> span, T oldItem, T newItem) where T : IEquatable<T>

It looks like all of them could actually be over IEquatable<T>, for example:

Span<byte> a = stackalloc byte[] { 1, 2, 3, 4, 5 };
ReadOnlySpan<byte> replacement = stackalloc byte[] { 0, 0, 0 };
ReadOnlySpan<byte> replacee = stackalloc byte[] { 2, 3 };
ReadOnlySpan<byte> buffer = stackalloc byte[256];
a.Replace(replacee, replacement, out var bufferSize);

// buffer => { 1, 0, 0, 0, 4, 5, ... }

I don't know if that is an API that makes sense, but in at least one case it seems to make sense to me. If warranted specialized implementations for char could be done that uses SIMD later.

[Gnbrkm41]

Great to see this idea catching on!

Related Issue: https://github.com/dotnet/corefx/issues/36460 (There were some additional discussions about span based overloads of replace)

[danmoseley]

Discussions also in #29111 and #22434

[HunteRoi]

Any news on the topic?

[IanKemp]

Sad that we're up to .NET 9 almost and no movement on this...

[Phylum123]

Isn't this what you are looking for?

https://learn.microsoft.com/en-us/dotnet/api/system.memoryextensions.replace?view=net-8.0

[wertzui]

MemoryExtensions.Replace takes arguments of type T and not ReadonlySpan<T>.