Add ImmutableArray Span-based APIs

[jamesqo]

EDIT see #22928 (comment) for the full API proposal.

@stephentoub You did not open a tracking issue for this in https://github.com/dotnet/corefx/issues/21281, although from the notes at dotnet/apireviews#40 it seems like this was approved (:tada:). So I took the liberty of moving the proposal here:

namespace System.Collections.Immutable
{
    public struct ImmutableArray<T>
    {
        public static implicit operator ReadOnlySpan<T>(ImmutableArray<T> array);
    }
}

Since the API seems to have been approved, this is intended to be a tracking issue for work towards implementing it.

[jamesqo]

@stephentoub I also wanted to open this issue since I noticed you wanted to add the following API to String:

namespace System
{
    public delegate void StringCreateAction<TState>(TState state, Span<char> destination);

    public class String
    {
        public static string Create<TState>(int length, TState state, StringCreateAction action);
        …
    }
}

Would it be worthwhile to add a similar method to create ImmutableArrays without copying as well?

[stephentoub]

You did not open a tracking issue for this in #22387

That's because I thought we said we weren't going to add anything related to collections right now. @terrajobst, did I miss that part of the discussion?

[airbreather]

Would it be worthwhile to add a similar method to create ImmutableArrays without copying as well?

If I understand this part of your suggestion properly, unlike with string, you can already build an ImmutableArray<T> of an initially known size reasonably efficiently with minimal copying:

ImmutableArray<int>.Builder builder = ImmutableArray.CreateBuilder<int>(17);
for (int i = 0; i < 17; i++)
{
    builder.Add(i);
}

ImmutableArray<int> built = builder.MoveToImmutable();

It does require allocating an ImmutableArray<T>.Builder, but otherwise it just holds the exact instance of T[] that is destined to back the final ImmutableArray<T> during MoveToImmutable().

Also, if someone really needed a ReadOnlySpan<T> and only had ImmutableArray<T>, they could bridge the gap themselves fairly easily, using a seemingly (to me) reasonable assumption that ImmutableArray<T> is going to have the underlying T[] as its first (edit: and only) field for a really long time:

using System;
using System.Collections.Immutable;
using System.Runtime.CompilerServices;

static class Program
{
    static void Main()
    {
        var array = CreateImmutableArray();
        UseSpan(array.AsSpan());
    }

    static ImmutableArray<int> CreateImmutableArray()
    {
        return new int[] { 1, 2, 3 }.ToImmutableArray();
    }

    static ReadOnlySpan<T> AsSpan<T>(this ImmutableArray<T> array)
    {
        return Unsafe.As<ImmutableArray<T>, T[]>(ref array);
    }

    static void UseSpan(ReadOnlySpan<int> span)
    {
        for (int i = 0; i < span.Length; i++)
        {
            Console.WriteLine(span[i]);
        }
    }
}

[NickStrupat]

I think something like immutability deserves a place in the BCL. Having developers roll their own is not a great solution given that immutability should impose the strongest guarantee.

I've implemented ImmutableMemory<T> and ImmutableSpan<T> as counterparts to their ReadOnly...<T> friends in System.Memory and there are a couple of edges that weren't super obvious.

Another thing to consider is that without these types in the BCL, developers may forget that ReadOnly...<T> types do not imply immutability of the underlying values. In other words, their existence makes the properties of ReadOnly...<T> more obvious.

[NickStrupat]

The nice thing is that they basically just wrap their counterparts with a couple of careful API choices.

public readonly struct ImmutableMemory<T>
{
	public ReadOnlyMemory<T> Memory { get; }
	public ImmutableMemory(ReadOnlySpan<T> source) => Memory = source.IsEmpty ? ReadOnlyMemory<T>.Empty : source.ToArray();
	private ImmutableMemory(ReadOnlyMemory<T> memory) => Memory = memory;

	public ImmutableSpan<T> ImmutableSpan => new ImmutableSpan<T>(this);

	public static ImmutableMemory<T> Empty { get; } = new ImmutableMemory<T>(ReadOnlySpan<T>.Empty);

	public Int32 Length => Memory.Length;
	public Boolean IsEmpty => Memory.IsEmpty;

	public void CopyTo(Memory<T> destination) => Memory.CopyTo(destination);
	[EditorBrowsable(EditorBrowsableState.Never)]
	public override Boolean Equals(Object obj) => obj is ImmutableMemory<T> im && Memory.Equals(im);
	public Boolean Equals(ImmutableMemory<T> other) => Memory.Equals(other.Memory);
	[EditorBrowsable(EditorBrowsableState.Never)]
	public override Int32 GetHashCode() => Memory.GetHashCode();
	public MemoryHandle Pin() => Memory.Pin();
	public ImmutableMemory<T> Slice(Int32 start, Int32 length) => new ImmutableMemory<T>(Memory.Slice(start, length));
	public ImmutableMemory<T> Slice(Int32 start) => new ImmutableMemory<T>(Memory.Slice(start));
	public T[] ToArray() => Memory.ToArray();
	public override String ToString() => Memory.ToString();
	public Boolean TryCopyTo(Memory<T> destination) => Memory.TryCopyTo(destination);

	public static implicit operator ImmutableMemory<T>(ArraySegment<T> segment) => new ImmutableMemory<T>(segment.AsSpan());
	public static implicit operator ImmutableMemory<T>(T[] array) => new ImmutableMemory<T>((ReadOnlySpan<T>) array);
}

public readonly ref struct ImmutableSpan<T>
{
	public ReadOnlySpan<T> Span { get; }
	public ImmutableSpan(ImmutableMemory<T> immutableMemory) => Span = immutableMemory.Memory.Span;
	private ImmutableSpan(ReadOnlySpan<T> span) => Span = span;
	public static ImmutableSpan<T> Empty => new ImmutableSpan<T>(ImmutableMemory<T>.Empty);

	public ref readonly T this[Int32 index] => ref Span[index];

	public Int32 Length => Span.Length;
	public Boolean IsEmpty => Span.IsEmpty;

	public void CopyTo(Span<T> destination) => Span.CopyTo(destination);

	[EditorBrowsable(EditorBrowsableState.Never)]
	[Obsolete("Equals() on ReadOnlySpan will always throw an exception. Use == instead.")]
	public override Boolean Equals(Object obj) => throw new NotSupportedException();

	public Enumerator GetEnumerator() => new Enumerator(this);

	[EditorBrowsable(EditorBrowsableState.Never)]
	[Obsolete("GetHashCode() on ReadOnlySpan will always throw an exception.")]
	public override Int32 GetHashCode() => throw new NotSupportedException();

	[EditorBrowsable(EditorBrowsableState.Never)]
	public ref readonly T GetPinnableReference() => ref Span.GetPinnableReference();
	public ImmutableSpan<T> Slice(Int32 start) => new ImmutableSpan<T>(Span.Slice(start));
	public ImmutableSpan<T> Slice(Int32 start, Int32 length) => new ImmutableSpan<T>(Span.Slice(start, length));
		
	public T[] ToArray() => Span.ToArray();
	public override String ToString() => Span.ToString();
	public Boolean TryCopyTo(Span<T> destination) => Span.TryCopyTo(destination);
		
	public static Boolean operator ==(ImmutableSpan<T> left, ImmutableSpan<T> right) => left.Span == right.Span;
	public static Boolean operator !=(ImmutableSpan<T> left, ImmutableSpan<T> right) => left.Span == right.Span;

	public static implicit operator ImmutableSpan<T>(T[] array) => new ImmutableSpan<T>((ImmutableMemory<T>) array);
	public static implicit operator ImmutableSpan<T>(ArraySegment<T> segment) => new ImmutableSpan<T>((ImmutableMemory<T>) segment);

	public ref struct Enumerator
	{
		private readonly ImmutableSpan<T> span;
		private int index;

		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		internal Enumerator(ImmutableSpan<T> span)
		{
			this.span = span;
			index = -1;
		}

		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		public bool MoveNext()
		{
			int index = this.index + 1;
			if (index < span.Length)
			{
				this.index = index;
				return true;
			}

			return false;
		}

		public ref readonly T Current {
			[MethodImpl(MethodImplOptions.AggressiveInlining)]
			get => ref span[index];
		}
	}
}

[mikernet]

ImmutableArray<T> ImmutableArray.Create<T>(ReadOnlySpan<T> span) would be rather handy to have to avoid the ceremony and overhead of allocating a builder and such.

[mikernet]

As well as a Builder.AddRange(ReadOnlySpan<T> span) method.

[333fred]

Just ran into another case where Builder.AddRange(ROS<T>) would be very nice. There has not been any movement on this for a couple years: @layomia what do we need to kick off design review? More concrete API proposals?

[333fred]

@eiriktsarpalis, Layomi said you would be the better person to answer: what are the next steps here? Do we need a more concrete API proposal?

[eiriktsarpalis]

Hi @333fred, next steps would be coming up with a finalized design for API review. Would you be interested in driving this?

[Joe4evr]

At a glance of the thread and existing APIs, it looks like this is the proposed design:

namespace System.Collections.Immutable
{
    public static partial class ImmutableArray
    {
+       public static ImmutableArray<T> Create<T>(ReadOnlySpan<T> items);
    }

    public partial struct ImmutableArray<T>
    {
        public sealed partial class Builder
        {
+           public void AddRange(ReadOnlySpan<T> items);

            // Unsure if this one is needed, but I'll list it just in case for proper parity
+           public void AddRange<TDerived>(ReadOnlySpan<TDerived> items) where TDerived : T;
        }
    }
}

[333fred]

@Joe4evr that's a start, but leaves out slicing (and possibly some other apis as well). It's on my plate to go through and do this, which I should get done in the next few days.

[333fred]

@eiriktsarpalis quick question: for sliceability, is the runtime's preference to an an indexer that takes a Range, or to add a Slice(int, int) method and get sliceability via the implicit language support?

[NickStrupat]

Any thoughts on my ImmutableSpan<T> idea? Immutable collections could all return ImmutableSpan<T> instead of ReadOnlySpan<T>, signalling to the calling code that the span of Ts will never change.

My apologies if I'm distracting from the main topic.

[alrz]

Are we going to return a span or another IA? I wonder why we didn't do that for arrays (GetSubArray), should this be consistent?

[333fred]

Any thoughts on my ImmutableSpan<T> idea? Immutable collections could all return ImmutableSpan<T> instead of ReadOnlySpan<T>, signalling to the calling code that the span of Ts will never change.

My apologies if I'm distracting from the main topic.

ImmutableArray doesn't make a guarantee of deep immutability today either. I don't see how ImmutableSpan would be any different than ReadOnlySpan, other than the name.

Ah, thinking on it for another minute I realize what you're going for: you're trying to communicate that slice[1] will always be the same instance, even if that instance itself is mutated more deeply. It's an interesting idea and worth thinking about in the review process as an alternative design, I think.

[mikernet]

Shouldn't indexers that take ranges return the same type, i.e. ImmutableArray in this case, to follow existing designs for arrays and strings and such? While I think that was a mistake (I would have much preferred if the default was performant and the more expensive operation required .ToString() or .ToArray() to be added after the range was taken), it's kind of a baked-in design decision at this point. If you want to slice IA and get a span then following the existing design you would do immutableArray.AsSpan()[1..6].

[mikernet]

Also love the idea of immutable spans. Would be great to have an immutable analogue to ROSpan that indicates the underlying list of items shouldn't change.

[terrajobst]

I'm not convinced that ImmutableSpan<T> would add a lot of value: spans are ref-structs, which means you can't stash them away easily. Hence their life time is fundamentally more constrained than regular collections. ImmutableMemory<T> is a different story, but considering the vast majority of the usages are for buffers which aren't immutable but only segregated into readers and writers, I don't think that such an abstraction would buy us much there either.

However, enriching ImmutableArray<T> with span-based APIs (as proposed in this issue) still makes sense.

[mikernet]

Right after I posted my comment I had the same thought about it being stack-only and thus perhaps overkill to have an immutable version but figured I would review my codebase more to see if I could see any actual potential benefits. It probably doesn't overcome the -100 test the more I think about it.

[stephentoub]

I agree with @terrajobst. Let's focus on adding the {ReadOnly}Span-based members, as well as Slice(int, int) (returning an ImmutableArray).

[airbreather]

I agree that this issue should probably focus on improving the relationship between ImmutableArray<T> and ReadOnlySpan<T>, as it has already evolved quite a lot over the years (to the point where I don't think that the single API in the issue description is even necessarily a good idea anymore, now that we have AsSpan()).

Regarding ImmutableSpan<T>, I don't think that the notion is completely without merit, even given that it would be stack-only. If I write a method that accepts a parameter of ImmutableArray<T> today, then I'm declaring that I need a contiguous block of T instances that nobody will ever modify, not even if they're running in a different thread. I recognize that the runtime environment cannot fully guarantee this, but I'm content with trusting callers to keep their hands off of the underlying array once it makes it to such a method.

This concept of "contiguous block of T instances that nobody will ever modify, not even if they're running in a different thread" only seems to be exposed via ImmutableArray<T>, which currently requires a new perfectly-sized T[] instance to sit behind it, even if the caller is perfectly suited to slice chunks out of a larger ImmutableArray<T> that came from somewhere else.

Again, though, there should probably be a separate issue for this kind of thing. I just wanted to jot down that potential usage scenario before I go crawling back into my cave again.

[333fred]

@terrajobst did you mean to have a Create(Span<T>) overload? I don't believe we wanted that. The ToImmutableArray overload makes sense, because it's an extension method. But the Create doesn't.

Nevermind, I have been reminded of the overload resolution implications for AsSpan.

[eiriktsarpalis]

Moving to 7.0.0, since it didn't make it to preview 7.

[lateapexearlyspeed]

Hi, I would like to learn and try this issue by PR. Will notify when it is ready for review, thanks.

[eiriktsarpalis]

Cool @lateapexearlyspeed, assigning the issue to you

[lateapexearlyspeed]

Hi, there are some questions during working on it, could anyone please help answer these, thanks :)

• public ReadOnlySpan AsSpan(Range range);

Range is from .netstandard2.1, but project System.Collections.Immutable and its ref project include target '.netstandard2.0', so how to add this new method into ?

• Existing RemoveRange(items) methods have following behaviors (I changed method logic so that existing test can report following output to describe previous behavior), so just confirm is previous logic as expected ? - only remove first occurrence element from array.

System.Collections.Immutable.Tests.ImmutableArrayTest.RemoveRangeEnumerable(source: [1, 2, 2, 3], items: [2], comparer: null) [FAIL]
Assert.Equal() Failure
Expected: ImmutableArray [1, 2, 3]
Actual: ImmutableArray [1, 3]

• Just wonder which methods should be the substitute for existing methods with IEnumerable<T> based argument so that users can efficiently pass their IEnumerable<T> for AddRange and RemoveRange ?

• I have synchronized apis for implementation and reference project of System.Collections.Immutable. But how to enable remote build pipeline for this breaking change PR by

ApiCompat failed comparing net5.0 to net7.0. If this breaking change is intentional, the ApiCompat baseline can be updated by running 'dotnet build /__w/1/s/src/libraries/shims/ApiCompat.proj /p:UpdatePreviousNetCoreAppBaseline=true'

[eiriktsarpalis]

Range is from .netstandard2.1, but project System.Collections.Immutable and its ref project include target '.netstandard2.0', so how to add this new method into ?

I believe the standard way of consuming Span types in netstandard2.0 projects is by consuming the System.Memory nuget package. Alternatively the APIs could be elided from the netstandard2.0 TFM, @terrajobst I presume the former is the preferred approach here?

[terrajobst]

Yeah, there is only one method that accepts a Range. Eliding that from .NET Standard 2.0 seems fine.

[lateapexearlyspeed]

Thanks @eiriktsarpalis and @terrajobst , skipped compilation for public ReadOnlySpan AsSpan(Range range); from .netstandard2.0.

Can anyone help answer other questions ?

• Existing RemoveRange(items) methods have following behaviors (I changed method logic so that existing test can report following output to describe previous behavior), so just confirm is previous logic as expected ? - only remove first occurrence element from array.

System.Collections.Immutable.Tests.ImmutableArrayTest.RemoveRangeEnumerable(source: [1, 2, 2, 3], items: [2], comparer: null) [FAIL]
Assert.Equal() Failure
Expected: ImmutableArray [1, 2, 3]
Actual: ImmutableArray [1, 3]

• Just wonder which methods should be the substitute for existing methods with IEnumerable<T> based argument so that users can efficiently pass their IEnumerable<T> for AddRange and RemoveRange ?
• I have synchronized apis for implementation and reference project of System.Collections.Immutable. But how to enable remote build pipeline for this breaking change PR by

ApiCompat failed comparing net5.0 to net7.0. If this breaking change is intentional, the ApiCompat baseline can be updated by running 'dotnet build /__w/1/s/src/libraries/shims/ApiCompat.proj /p:UpdatePreviousNetCoreAppBaseline=true'

[airbreather]

Thanks @eiriktsarpalis and @terrajobst , skipped compilation for public ReadOnlySpan AsSpan(Range range); from .netstandard2.0.

Can anyone help answer other questions ?

I was going to let the experienced members of the team weigh in instead of commenting myself, since I'm just some random guy, but since it's been a few days... I expect the dotnet team to reject breaking changes like the ones you're asking about, especially when they're such hard breaks as removing AddRange(IEnumerable<T>) and RemoveRange(IEnumerable<T>) would be.

From my perspective, it looks like you might have misinterpreted #22928 (comment)? The methods that are commented-out in that reference description probably weren't meant to be treated as "remove these methods", but rather "these methods already exist, so you don't need to add them for this".

• The discussion about breaking changes actually centers around a much softer breaking change, where I believe that adding the new overloads could make it so that immArray = immArray.AddRange(myCustomThing); compiles just fine today, but would be ambiguous after the change, for some unlikely values of myCustomThing.
• That breaking change, where something that's currently unambiguous becomes ambiguous, is the only breaking change that I can see being accepted, and I agree with that decision FWIW.

I could be mistaken, which is again why I was holding off on commenting, but I do have an interest in these new APIs, and I would very much appreciate the IEnumerable<T> versions sticking around...

[eiriktsarpalis]

@airbreather's interpretation is accurate, apologies for not clarifying this earlier.

[terrajobst]

The methods that are commented-out in that reference description probably weren't meant to be treated as "remove these methods", but rather "these methods already exist, so you don't need to add them for this".

That is correct. I often add those for context, in order to judge how the new APIs compose with (the relevant subset of) the existing APIs.

That breaking change, where something that's currently unambiguous becomes ambiguous, is the only breaking change that I can see being accepted, and I agree with that decision FWIW.

Agreed. We try to avoid source breaking changes like this, but we accept them when there is no other way to make progress. That is, we prefer creating designs that don't cause them, but we're also trying to avoid design-paralysis or frankendesigns purely because some source code would need a cast.

[lateapexearlyspeed]

Thanks @airbreather's interpretation.

[lateapexearlyspeed]

Hi, this PR is ready for review, thanks !