Implement all companion APIs for System.Index and System.Range

[terrajobst]

The spec is here.

Preview 1 Shipped Version

namespace System
{
    public readonly partial struct Index : IEquatable<Index>
    {
        public Index(int value, bool fromEnd); // well-known
        public bool FromEnd { get; }           // well-known
        public int Value { get; }              // well-known
        public bool Equals(Index other);
        public override bool Equals(object value);
        public override int GetHashCode();
        public static implicit operator Index (int value);
        public override string ToString();
    }

    public readonly partial struct Range : IEquatable<Range>
    {
        public Index End { get; }                           // well-known
        public Index Start { get; }                         // well-known
        public static Range All();                          // well-known
        public static Range Create(Index start, Index end); // well-known
        public override bool Equals(object value);
        public bool Equals(Range other);
        public static Range FromStart(Index start);         // well-known
        public override int GetHashCode();
        public static Range ToEnd(Index end);               // well-known
        public override string ToString();
    }
}

Open Issues

• Finalize the list of the types will have indexers using Index and Range
• Index type has public constructor while Range using Factory methods to create Range. Should we make the types consistent? either have constructors on both or Factory methods on both. or having constructors and factory methods on both.
• Should we have helper methods on Range for calculating the range length? GetLength(int containerLength) or Range Close(int containerLength)
• Does Index or Range need to implement any more interfaces?
• Confirm it is desirable that ^0 in the range is pointing at beyond last element of the container.
• Add helper for Range array creation that allocates a new array of the appropriate size and copies the elements from the first array into the new array

[stephentoub]

@terrajobst, is that the full list? I'm wondering if we're planning to, for example, add such Index-based indexers to collections like List<T>.

[terrajobst]

It's the full list of what I had planned. But you're right. We should probably add more, such as:

• List, ArraySegment, for perf
• IList, IReadOnlyList, at least an indexer for Index. Not sure about Range. We'd have to decide what the return type would be.
  • Via default interface implementation.

It might be worthwhile to discuss this.

[AndyAyersMS]

Any goals around perf?

Methods using Index need to be implemented carefully to work well in concert with the jit and depending on perf goals may require some jit improvements (see for instance dotnet/coreclr#21196).

Haven't looked at Range in depth yet but suspect similar concerns apply, and possibly more...

[stephentoub]

Haven't looked at Range in depth yet but suspect similar concerns apply, and possibly more...

For all of these additional types other than ArraySegment, I'm still not excited about providing Range-based indexers, just like I'm not excited about it for string and T[]. They're going to have terrible perf, yet look enticing and will be easily accidentally used.

[tarekgh]

@terrajobst

It's the full list of what I had planned. But you're right. We should probably add more, such as:

Please update the specs if you think we need to add more types to the list. I'll start working on that soon.

[benaadams]

IList, IReadOnlyList ... Via default interface implementation.

Something like this?

public static class RangeExtensions
{
    public static RangeSlice<TList, T> Slice<TList, T>(this TList list, Range range)
        where TList : IList<T>
    {
        int start = range.Start.FromEnd ? list.Count - range.Start.Value : range.Start.Value;
        int end = range.End.FromEnd ? list.Count - range.End.Value : range.End.Value;

        return new RangeSlice<TList, T>(list, start, end);
    }

    public struct RangeSlice<TList, T>
        where TList : IList<T>
    {
        private readonly TList _list;
        private readonly int _start;
        private readonly int _end;

        internal RangeSlice(TList list, int start, int end)
        {
            if (list == null)
            {
                throw new ArgumentNullException(nameof(list));
            }
            if (start < 0 || start >= list.Count)
            {
                throw new IndexOutOfRangeException(nameof(start));
            }
            if (end < start || end >= list.Count)
            {
                throw new IndexOutOfRangeException(nameof(end));
            }
            _list = list;
            _start = start;
            _end = end;
        }

        public T this[int index]
        {
            get => _list[GetIndex(index)];
            set => _list[GetIndex(index)] = value;
        }

        private int GetIndex(int index)
        {
            checked
            {
                int newIndex = index + _start;
                if (newIndex >= _end)
                {
                    throw new IndexOutOfRangeException();
                }

                return newIndex;
            }
        }

        public int Count => _start - _end;

        public Enumerator GetEnumerator() => new Enumerator(_list, _start, _end);

        public struct Enumerator : IEnumerator<T>
        {
            private readonly TList _list;
            private readonly int _start;
            private readonly int _end;

            private int _index;

            internal Enumerator(TList list, int start, int end)
            {
                _list = list;
                _start = start;
                _end = end;
                _index = start - 1;
                Current = default;
            }

            public T Current { get; private set; }

            public bool MoveNext()
            {
                checked
                {
                    _index++;
                }

                if (_index < _end)
                {
                    Current = _list[_index];
                    return true;
                }

                Current = default;
                return false;
            }

            public void Dispose(){}
            object IEnumerator.Current => Current;
            void IEnumerator.Reset() => _index = _start - 1;
        }
    }
}

Though perf would be worse than C# just translating it, especially since it will likely be interface dispatch (shared generic) rather than direct calls (specialised generic).

[benaadams]

Would be nice if there was a faster way of capturing this in the type system via C# without rewriting it

e.g. converting the nice

foreach (var item in list[range])
{
    // do something with item
} 

To the less nice, but concretely typed

int start = range.Start.FromEnd ? list.Count - range.Start.Value : range.Start.Value;
int end = range.End.FromEnd ? list.Count - range.End.Value : range.End.Value;

for (var i = start; i < end; i++)
{
     var item = list[i];
    // do something with item
}

In csharplang the community would tell me shapes would solve the perf 😉

[Joe4evr]

I feel like Range.FromStart(Index start) and Range.ToEnd(Index end) are misnamed. If I were to write Range.ToEnd(5), what I intuitively expect is to get a Range representing all elements from 5 to the end of the collection, but instead it looks like it'd return a Range representing 0..5, which is the complete and total opposite.

My suggestion would be to adjust the names to be clearer, though it would switch around which does what: Range FromStartTo(Index end) and Range ToEndFrom(Index start). This way Range.FromStartTo(5) is equivalent to 0..5 and Range.ToEndFrom(5) is equivalent to 5.. without confusion.

[terrajobst]

This work was discussed and completed by @tarekgh.