C# 8.0 in-depth: Understanding index and range, and working with LINQ and IEnumerable<T>

C# 8.0 introduces index and range for array. This part discussed the index and range types, syntax, compilation, and how to apply them with LINQ for any type that implements IEnumerable.

Index and Range types and C# syntax#

The System.Index and System.Range structures are introduced to the new .NET Standard. Index is a wrapper of int index value (non-negative int means index from start, negative int means index from the end), and Range is a tuple of start Index and end Index:

1
public readonly struct Index : IEquatable<Index>
2
{
3
    private readonly int _value;
4

5
    public Index(int value, bool fromEnd)
6
    {
7
        if (value < 0)
8
        {
9
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();
10
        }
11
        this._value = fromEnd ? ~value : value;
12
    }
13

14
    public int Value => this._value >= 0 ? this._value : ~this._value;
15

16
    public bool FromEnd => _value < 0;
17

18
    public static implicit operator Index(int value) => new Index(value, false);
19

20
    // Other members.
21
}
22

23
public readonly struct Range : IEquatable<Range>
24
{
25
    private Range(Index start, Index end)
26
    {
27
        this.Start = start; this.End = end;
28
    }
29

30
    public Index Start { get; }
31

32
    public Index End { get; }
33

34
    public static Range Create(Index start, Index end) =>
35
        new Range(start, end);
36

37
    public static Range All() =>
38
        new Range(new Index(0, false), new Index(0, true));
39

40
    // Other members.
41
}

C# 8.0 introduces the index and range syntax:

1
Index index1 = 1; // Index 1 from start.
2
Index index2 = ^2; // Index 2 from end.
3
Range range1 = 1..10; // Start index is 1 from start, end index is 10 from start.
4
Range range2 = 10..^5; // Start index is 1 from start, end index is 5 from end.
5
Range range3 = ^10..; // Start index is 10 from end, end index is 0 from end.
6
Range range4 = ..; // Start index is 0 from start, end index is 0 from end.

These are syntactic sugars, which are compiled to:

1
Index index3 = 1;
2
Index index2 = new Index(2, true);
3
Range range5 = Range.Create(1, 10);
4
Range range4 = Range.Create(10, new Index(5, true));
5
Range range3 = Range.FromStart(new Index(10, true));
6
Range range2 = Range.All();

Index and Range for array#

C# introduces syntactic sugars to enable Index with array:

1
int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
2
int value = array[^1];

It is compiled to normal int indexer access:

1
int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
2
Index index = new Index(1, true);
3
int value = index.FromEnd ? array[array.Length - index.Value] : array[index.Value];

And this is the range syntactic sugar for array slice:

1
int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
2
int[] slice = array[^9..7];

It is compiled to array copy:

1
int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
2
Range range = Range.Create(new Index(9, true), 7);
3
int startIndex = range.Start.FromEnd ? array.Length - range.Start.Value : range.Start.Value;
4
int rangeLength = (range.End.FromEnd ? array.Length - range.End.Value : range.End.Value) - startIndex;
5
int[] slice = new int[rangeLength];
6
Array.Copy(sourceArray: array, sourceIndex: startIndex, destinationArray: slice, destinationIndex: 0, length: rangeLength);

LINQ queries - Index and Range for IEnumerable#

Currently (v3.0.0-preview2/SDK 3.0.100-preview-010184), the index and range work with array, and do not work with other types, like List. It is natural and convenient to support index and range in LINQ, so they can work with any type that implements IEnumerable. The goals of these LINQ APIs are:

Use index to locate an element in sequence, use range to slice sequence. The usage is the same as index/range for array, but with deferred execution for slice with range.
Use range to start fluent LINQ query.

This enables the index and range to work with any type that implements IEnumerable.

LINQ already has ElementAt(int index) and ElementOrDefault(int index) query operator. It would be natural to have a overload for System.Index: ElementAt(Index index) and ElementOrDefault(Index index), and a new method ElementsIn(Range range), so that LINQ can seamlessly work with C# 8.0:

1
Index index = ...;
2
var element1 = source1.ElementAt(index);
3
var element2 = source2.ElementAtOrDefault(^ 5);
4
Range range = ...;
5
var slice1 = source3.ElementsIn(range);
6
var slice2 = source4.ElementsIn(2..^ 2)
7
var slice2 = source5.ElementsIn(^ 10..);

The following Range overload and AsEnumerable overload for System.Range convert it to a sequence, so that LINQ query can be started fluently from c# range:

1
Index index = ...;
2
var element1 = source1.ElementAt(index);
3
var element2 = source2.ElementAtOrDefault(^ 5);
4
Range range = ...;
5
var slice1 = source3.ElementsIn(range);
6
var slice2 = source4.ElementsIn(2..^ 2)
7
var slice2 = source5.ElementsIn(^ 10..);

APIs#

For LINQ to Objects, ideally:

1
namespace System.Linq
2
{
3
    public static partial class Queryable
4
    {
5
        public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, Index index) { throw null; }
6

7
        public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, Index index) { throw null; }
8

9
        public static IEnumerable<TSource> ElementsIn<TSource>(this IEnumerable<TSource> source, Range range) { throw null; }
10

11
        public static IEnumerable<TSource> Range<TSource>(Range range) { throw null; }
12

13
        public static IEnumerable<TSource> AsEnumerable<TSource>(this Range source) { throw null; }
14
    }
15
}

For remote LINQ, ideally:

1
namespace System.Linq
2
{
3
    public static partial class Queryable
4
    {
5
        public static TSource ElementAt<TSource>(this IQueryable<TSource> source, Index index) { throw null; }
6

7
        public static TSource ElementAtOrDefault<TSource>(this IQueryable<TSource> source, Index index) { throw null; }
8

9
        public static IQueryable<TSource> ElementsIn<TSource>(this IQueryable<TSource> source, Range range) { throw null; }
10
    }
11
}

Implementation details#

These APIs’ implementation is self-contained so that the code can be just copied to use.

The implementation of ElementAt(Index), ElementOrDefault(Index) and ElementsIn(Range) for IQueryable is straightforward. They just create an expression tree.

1
internal static class QueryableExtensions
2
{
3
    public static TSource ElementAt<TSource>(this IQueryable<TSource> source, Index index)
4
    {
5
        if (source == null)
6
            // throw Error.ArgumentNull(nameof(source));
7
            throw new ArgumentNullException(nameof(source));
8
        return source.Provider.Execute<TSource>(
9
            Expression.Call(
10
                null,
11
                CachedReflectionInfo.ElementAt_TSource_2(typeof(TSource)),
12
                source.Expression, Expression.Constant(index)
13
                ));
14
    }
15

16
    public static TSource ElementAtOrDefault<TSource>(this IQueryable<TSource> source, Index index)
17
    {
18
        if (source == null)
19
            // throw Error.ArgumentNull(nameof(source));
20
            throw new ArgumentNullException(nameof(source));
21
        return source.Provider.Execute<TSource>(
22
            Expression.Call(
23
                null,
24
                CachedReflectionInfo.ElementAtOrDefault_TSource_2(typeof(TSource)),
25
                source.Expression, Expression.Constant(index)
26
                ));
27
    }
28

29
    public static IQueryable<TSource> ElementsIn<TSource>(this IQueryable<TSource> source, Range range)
30
    {
31
        if (source == null)
32
            // throw Error.ArgumentNull(nameof(source));
33
            throw new ArgumentNullException(nameof(source));
34

35
        return source.Provider.CreateQuery<TSource>(
36
            Expression.Call(
37
                null,
38
                CachedReflectionInfo.ElementsIn_TSource_2(typeof(TSource)),
39
                source.Expression, Expression.Constant(range)));
40
    }
41
}
42

43
internal static class CachedReflectionInfo
44
{
45
    private static MethodInfo s_ElementAt_TSource_2;
46

47
    public static MethodInfo ElementAt_TSource_2(Type TSource) =>
48
         (s_ElementAt_TSource_2 ??
49
         (s_ElementAt_TSource_2 = new Func<IQueryable<object>, Index, object>(QueryableExtensions.ElementAt).GetMethodInfo().GetGenericMethodDefinition()))
50
          .MakeGenericMethod(TSource);
51

52
    private static MethodInfo s_ElementAtOrDefault_TSource_2;
53

54
    public static MethodInfo ElementAtOrDefault_TSource_2(Type TSource) =>
55
         (s_ElementAtOrDefault_TSource_2 ??
56
         (s_ElementAtOrDefault_TSource_2 = new Func<IQueryable<object>, Index, object>(QueryableExtensions.ElementAtOrDefault).GetMethodInfo().GetGenericMethodDefinition()))
57
          .MakeGenericMethod(TSource);
58

59
    private static MethodInfo s_ElementsIn_TSource_2;
60

61
    public static MethodInfo ElementsIn_TSource_2(Type TSource) =>
62
         (s_ElementsIn_TSource_2 ??
63
         (s_ElementsIn_TSource_2 = new Func<IQueryable<object>, Range, IQueryable<object>>(QueryableExtensions.ElementsIn).GetMethodInfo().GetGenericMethodDefinition()))
64
          .MakeGenericMethod(TSource);
65
}

These methods for IEnumerable are straightforward as well, I just followed the behavior and exceptions of array with range. See unit tests https://github.com/Dixin/CodeSnippets/blob/master/Linq.Range/Linq.Range.Tests/ElementsInTests.cs.

ElementAt(Index) and ElementAtOrDefault(Index):

1
public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, Index index)
2
{
3
    if (source == null)
4
    {
5
        // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
6
        throw new ArgumentNullException(nameof(source));
7
    }
8

9
    if (!index.FromEnd)
10
    {
11
        return source.ElementAt(index.Value);
12
    }
13

14
    int indexFromEnd = index.Value;
15
    if (indexFromEnd > 0)
16
    {
17
        if (source is IList<TSource> list)
18
        {
19
            return list[list.Count - indexFromEnd];
20
        }
21

22
        using (IEnumerator<TSource> e = source.GetEnumerator())
23
        {
24
            if (e.MoveNext())
25
            {
26
                Queue<TSource> queue = new Queue<TSource>();
27
                queue.Enqueue(e.Current);
28
                while (e.MoveNext())
29
                {
30
                    if (queue.Count == indexFromEnd)
31
                    {
32
                        queue.Dequeue();
33
                    }
34

35
                    queue.Enqueue(e.Current);
36
                }
37

38
                if (queue.Count == indexFromEnd)
39
                {
40
                    return queue.Dequeue();
41
                }
42
            }
43
        }
44
    }
45

46
    // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
47
    throw new ArgumentOutOfRangeException(nameof(index));
48
    return default!;
49
}
50

51
public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, Index index)
52
{
53
    if (source == null)
54
    {
55
        // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
56
        throw new ArgumentNullException(nameof(source));
57

58
    }
59

60
    if (!index.FromEnd)
61
    {
62
        return source.ElementAtOrDefault(index.Value);
63
    }
64

65
    int indexFromEnd = index.Value;
66
    if (indexFromEnd > 0)
67
    {
68
        if (source is IList<TSource> list)
69
        {
70
            int count = list.Count;
71
            if (count >= indexFromEnd)
72
            {
73
                return list[count - indexFromEnd];
74
            }
75
        }
76

77
        using (IEnumerator<TSource> e = source.GetEnumerator())
78
        {
79
            if (e.MoveNext())
80
            {
81
                Queue<TSource> queue = new Queue<TSource>();
82
                queue.Enqueue(e.Current);
83
                while (e.MoveNext())
84
                {
85
                    if (queue.Count == indexFromEnd)
86
                    {
87
                        queue.Dequeue();
88
                    }
89

90
                    queue.Enqueue(e.Current);
91
                }
92

93
                if (queue.Count == indexFromEnd)
94
                {
95
                    return queue.Dequeue();
96
                }
97
            }
98
        }
99
    }
100

101
    return default!;
102
}

ElementsIn(Range):

1
public static IEnumerable<TSource> ElementsIn<TSource>(this IEnumerable<TSource> source, Range range)
2
{
3
    if (source == null)
4
    {
5
        // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
6
        throw new ArgumentNullException(nameof(source));
7
    }
8

9
    return ElementsInIterator(source, range);
10
}
11

12
private static IEnumerable<TSource> ElementsInIterator<TSource>(IEnumerable<TSource> source, Range range)
13
{
14
    Index start = range.Start;
15
    Index end = range.End;
16

17
    if (source is IList<TSource> list)
18
    {
19
        int count = list.Count;
20
        if (count == 0 && range.Equals(System.Range.All()))
21
        {
22
            yield break;
23
        }
24

25
        int firstIndex = start.FromEnd ? count - start.Value : start.Value;
26
        int lastIndex = (end.FromEnd ? count - end.Value : end.Value) - 1;
27
        if (lastIndex < firstIndex - 1)
28
        {
29
            // ThrowHelper.ThrowOverflowException();
30
            throw new OverflowException(); // Following the behavior of array with range.
31
        }
32

33
        if (firstIndex < 0 || lastIndex < 0)
34
        {
35
            // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
36
            throw new ArgumentOutOfRangeException(nameof(range)); // Following the behavior of array with range.
37
        }
38

39
        if (firstIndex >= count || lastIndex >= count)
40
        {
41
            // ThrowHelper.ThrowArgumentException(ExceptionArgument.range);
42
            throw new ArgumentException(nameof(range)); // Following the behavior of array with range.
43
        }
44

45
        for (int currentIndex = firstIndex; currentIndex <= lastIndex; currentIndex++)
46
        {
47
            yield return list[currentIndex];
48
        }
49
        yield break;
50
    }
51

52
    using (IEnumerator<TSource> e = source.GetEnumerator())
53
    {
54
        int currentIndex = -1;
55
        if (start.FromEnd)
56
        {
57
            if (!e.MoveNext())
58
            {
59
                const int count = 0;
60
                int firstIndex = count - start.Value;
61
                int lastIndex = (end.FromEnd ? count - end.Value : end.Value) - 1;
62
                if (lastIndex < firstIndex - 1)
63
                {
64
                    // ThrowHelper.ThrowOverflowException();
65
                    throw new OverflowException(); // Following the behavior of array with range.
66
                }
67

68
                // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
69
                throw new ArgumentOutOfRangeException(nameof(range));
70
            }
71
            else
72
            {
73
                Queue<TSource> queue = new Queue<TSource>();
74
                queue.Enqueue(e.Current);
75
                currentIndex++;
76

77
                int takeLastCount = start.Value;
78
                while (e.MoveNext())
79
                {
80
                    if (queue.Count == takeLastCount)
81
                    {
82
                        queue.Dequeue();
83
                    }
84

85
                    queue.Enqueue(e.Current);
86
                    currentIndex++;
87
                }
88

89
                if (queue.Count < takeLastCount)
90
                {
91
                    // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
92
                    throw new ArgumentOutOfRangeException(nameof(range));
93
                }
94

95
                int firstIndex = currentIndex + 1 - takeLastCount;
96
                int lastIndex = end.FromEnd ? currentIndex - end.Value : end.Value - 1;
97
                if (lastIndex < firstIndex - 1)
98
                {
99
                    // ThrowHelper.ThrowOverflowException();
100
                    throw new OverflowException(); // Following the behavior of array with range.
101
                }
102

103
                for (int index = firstIndex; index <= lastIndex; index++)
104
                {
105
                    yield return queue.Dequeue();
106
                }
107
            }
108
        }
109
        else
110
        {
111
            int firstIndex = start.Value;
112
            if (!e.MoveNext())
113
            {
114
                if (range.Equals(System.Range.All()))
115
                {
116
                    yield break;
117
                }
118

119
                const int count = 0;
120
                int lastIndex = (end.FromEnd ? count - end.Value : end.Value) - 1;
121
                if (lastIndex < firstIndex - 1)
122
                {
123
                    // ThrowHelper.ThrowOverflowException();
124
                    throw new OverflowException(); // Following the behavior of array with range.
125
                }
126
                // ThrowHelper.ThrowArgumentException(ExceptionArgument.range);
127
                throw new ArgumentException(nameof(range)); // Following the behavior of array with range.
128
            }
129

130
            currentIndex++;
131
            while (currentIndex < firstIndex && e.MoveNext())
132
            {
133
                currentIndex++;
134
            }
135

136
            if (currentIndex != firstIndex)
137
            {
138
                // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
139
                throw new ArgumentOutOfRangeException(nameof(range));
140
            }
141

142
            if (end.FromEnd)
143
            {
144
                int skipLastCount = end.Value;
145
                if (skipLastCount > 0)
146
                {
147
                    Queue<TSource> queue = new Queue<TSource>();
148
                    do
149
                    {
150
                        if (queue.Count == skipLastCount)
151
                        {
152
                            yield return queue.Dequeue();
153
                        }
154

155
                        queue.Enqueue(e.Current);
156
                        currentIndex++;
157
                    }
158
                    while (e.MoveNext());
159
                }
160
                else
161
                {
162
                    do
163
                    {
164
                        yield return e.Current;
165
                        currentIndex++;
166
                    }
167
                    while (e.MoveNext());
168
                }
169

170
                if (firstIndex + skipLastCount > currentIndex)
171
                {
172
                    // ThrowHelper.ThrowOverflowException();
173
                    throw new OverflowException(); // Following the behavior of array with range.
174
                }
175
            }
176
            else
177
            {
178
                int lastIndex = end.Value - 1;
179
                if (lastIndex < firstIndex - 1)
180
                {
181
                    // ThrowHelper.ThrowOverflowException();
182
                    throw new OverflowException(); // Following the behavior of array with range.
183
                }
184

185
                if (lastIndex == firstIndex - 1)
186
                {
187
                    yield break;
188
                }
189

190
                yield return e.Current;
191
                while (currentIndex < lastIndex && e.MoveNext())
192
                {
193
                    currentIndex++;
194
                    yield return e.Current;
195
                }
196

197
                if (currentIndex != lastIndex)
198
                {
199
                    // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
200
                    throw new ArgumentOutOfRangeException(nameof(range));
201
                }
202
            }
203
        }
204
    }
205
}

For Range(Range) and AsEnumerable(Range), the question is: what does Range’s start Index and end Index mean when the index is from the end? For example, 10..20 can be easily converted to a sequence of 10, 11,12, … 19, but how about ^20…^10? In my current implementation, regarding Index’s value can be from 0 to int.MaxValue, I assume a virtual “full range” 0..2147483648, and any Range instance is a slice of that “full range”. So:

Ranges .. and 0.. and ..^0 and 0..^0 are converted to “full sequence” 0, 1, .. 2147483647
Range 100..^47 is converted to sequence 100, 101, .. 2147483600
Range ^48..^40 is converted to sequence 2147483600, 2147483601 .. 2147483607
Range 10..10 is converted to empty sequence

etc.

1
public static IEnumerable<int> Range(Range range)
2
{
3
    Index startIndex = range.Start;
4
    Index endIndex = range.End;
5
    int firstValue = startIndex.FromEnd ? int.MaxValue - startIndex.Value + 1 : startIndex.Value;
6
    int lastValue = endIndex.FromEnd ? int.MaxValue - endIndex.Value : endIndex.Value - 1;
7
    if (lastValue < firstValue - 1)
8
    {
9
        // ThrowHelper.ThrowOverflowException();
10
        throw new OverflowException(); // Following the behavior of array with range.
11
    }
12

13
    if (lastValue == firstValue - 1)
14
    {
15
        return Enumerable.Empty<int>();
16
    }
17

18
    return RangeIterator(firstValue, lastValue);
19
}
20

21
private static IEnumerable<int> RangeIterator(int firstValue, int lastValue)
22
{
23
    for (int value = firstValue; value <= lastValue; value = checked(value + 1))
24
    {
25
        yield return value;
26
        if (value == int.MaxValue)
27
        {
28
            yield break;
29
        }
30
    }
31
}
32

33
public static IEnumerable<int> AsEnumerable(this Range range)
34
{
35
    int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
36
    int[] slice = array[^ 9..7];
37
    return Range(range);
38
}

See unit tests of AsEnumerable(Range) https://github.com/Dixin/CodeSnippets/blob/master/Linq.Range/Linq.Range.Tests/AsEnumerableTests.cs.