Runtime: Proposal (& implementation): LINQ APIs to enable C# 8.0 index and range for IEnumerable<T>

[Dixin]

C# 8.0 introduces index and range features for array and countable types. It is natural and convenient to generally support index and range for all IEnumerable types and LINQ. I searched the API review notes, didn't find such APIs, so propose them here.

var element = source1.ElementAt(index: ^5);
var elements = source2.ElementsIn(range: 10..^10); // or Slice(10..^10)
var query1 = Enumerable.Range(10..20).Select().Where();
var query2 = (10..20).AsEnumerable().Select().Where();

Problem

Index/range are language level features. Currently, they

• work with array, (compiled to member copy for array with the help of Span)
• work with for countable type: https://github.com/dotnet/csharplang/blob/master/proposals/index-range-changes.md
• do not work with "uncountable" IEnumerable<T> types or LINQ query.

Rationale and usage

The goals of these LINQ APIs are:

• Use index to locate an element in sequence.
• Use range to slice a sequence. The usage should be consistent with array, but with deferred execution.
• Use range to start fluent LINQ query.

This enables index and range language features to work with any type that implements IEnumerable<T>.

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

Index index = ...;
var element1 = source1.ElementAt(index);
var element2 = source2.ElementAtOrDefault(^5);
Range range = ...;
var slice1 = source3.ElementsIn(range); // or Slice(range)
var slice2 = source4.ElementsIn(2..^2); // or Slice(2..^2)
var slice2 = source5.ElementsIn(^10..); // or Slice(^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:

var query1 = Enumerable.Range(10..).Select(...);
Range range = ...;
var query2 = range.AsEnumerable().Select(...);
var query3 = (10..20).AsEnumerable().Where(...);

With these APIs, the C# [index] and [range] syntax can be possibly enabled for sequence as well.

Proposed APIs

For LINQ to Objects:

namespace System.Linq
{
    public static partial class Enumerable
    {
        public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, Index index) { throw null; }

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

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

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

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

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

For remote LINQ:

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

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

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

        public static IQueryable<TSource> Slice<TSource>(this IQueryable<TSource> source, Range range) { throw null; }
    }
}

Implementation details (and pull request)

The API review process says PR should not be submitted before the API proposal is approved. So currently I implemented these APIs separately https://github.com/Dixin/Linq.IndexRange :

• Enumerable: ElementAt(Index), ElementAtOrDefault(Index)
• Enumerable: ElementsIn(Range) and Slice(Range)
• Enumerable: Range(Range) and AsEnumerable(Range). They are the same conversion.
• Queryable: ElementAt(Index), ElementAtOrDefault(Index), ElementsIn(Range), Slice(Range).

So that anyone can start to use these APIs by adding a NuGet package:

dotnet add package Linq.IndexRange --version 1.0.0-preview4

If this proposal is doable, I can submit a PR quickly.

The implementation of ElementAt(Index), ElementAtOrDefault(Index) and ElementsIn(Range) for IQueryable<T> is straightforward. They just create an expression tree. ElementAt(Index) and ElementAtOrDefault(Index) for IEnumerable<T> are straightforward as well.

Open questions

ElementsIn(Range) vs Slice(Range) as name

Should ElementsIn(Range) be called Slice? Currently I implemented both.

• ElementsIn(Range range) maintains the naming consistency with original ElementAt(int index), which could be natural for existing LINQ users.
• The naming of Slice is consistent with the proposal for countable types, which requires a `Slice member.

Out of range handling

What should we do when the range's start index and/or end index go off the boundaries of source sequence? There are 2 options:

• Array behavior: Follow the behavior of range with array, and throw OverflowException/ArgumentEception/ArgumentOutOfRangeException accordingly. I implemented ElementsIn(Range) following this array behavior. See unit tests of ElementsIn.
• LINQ behavior: Follow the behavior of current partitioning LINQ operators like Skip/Take/SkipLast/TakeLast, which do not throw exception. I implemented Slice following this LINQ behavior. See unit test of Slice.

ElementAt(Index) and Queryable

As @bartdesmet mentioned in the comments, LINQ providers may have issues when they see ElementAt having an Index argument, etc. Should we have a new name for the operator instead of overload? For example, At(Index) or Index(Index)?

Range

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?

The easiest way is to disallow, and throw exception.

My current implementation attempts to make it flexible. 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. See unit tests of Range(Range).

AsEnumerable

Should this be provided to bridge range to LINQ? For me, at least (10..20).AsEnumerable().Select().Where() is intuitive and natural.

[bartdesmet]

This looks interesting to me and has been on my list of things to look into for Ix and async LINQ for IAsyncEnumerable<T> over at https://github.com/dotnet/reactive/pull/423. Adding @terrajobst for visibility, given he owns System.Index and System.Range and is also aware of the work in Ix.

From a technical point of view, here are my 0.02 cents:

ElementAt and ElementAtOrDefault

These do make sense and have little ambiguity. Indexing from the end is also not a concern, given TakeLast was also added to LINQ surface before. It'd be nice to define some algebraic identities, e.g. converting ElementAt[OrDefault](i) to Skip(n).First[OrDefault]() if indexing from the start or SkipLast(n).Last[OrDefault]() if indexing from the end, at least for purposes of reviewing a design (and to write tests to assert the identity, though likely not for an implementation when it comes to efficiency).

ElementsIn

This one is a bit more fuzzy. At first glance, it feels like a Slice method and obeys, as a first approximation, to the identity xs.Slice(r).SequenceEqual(xs.ToArray().Slice(r)), except for infinite sequences where ToArray wouldn't terminate. In this case, there'd be exceptions thrown for range violations. Likely ArgumentOutOfRangeException to match existing LINQ operators, rather than OverflowException or something like that.

Alternatively, the identity could be defined in terms of composing Skip[Last] and Take[Last]. However, that'd bring with it other exception behavior (namely, none), because Skip and Take are happy to yield empty sequences.

So the question would be whether to lean towards array semantics or LINQ semantics, and an argument could be made for both sides (though, also based on the Range discussion below, I'd be leaning towards the former).

Range and AsEnumerable

A first question is whether Range implementing IEnumerable<int> would make sense. Most likely not, because "from end" values. Would these be relative to int.MaxValue (as in the open question raised here), which yields integers that are not relative to some list-like thing being indexed into (which is the primary use of Range)? Given this observation, I'm not the biggest fan of an AsEnumerable extension method on Range because it could/would give the false illusion of "if Range were to implement IEnumerable, it'd do it like this".

As for Enumerable.Range, that could make sense given it would be clearer than start, count pairs where one often wonders if the second argument to Range is an index or a count (.. eliminates this confusion). I actually always use named parameters when calling Range to clarify the meaning of the two integer arguments.

Supporting "from end" is a different matter though. On the one hand, given the int return type, one could "suspect" a range 0..int.MaxValue, but a more formally inclined person could argue about the signed nature of int (int.MinValue..int.MaxValue?). I'd personally not be offended by Range throwing Argument[OutOfRange]Exception to indicate there's no "from end" support, and just have it work for cases that would already be expressible using current the Enumerable.Range method, i.e. relative to 0. Open-ended ranges are still a question then, either picking int.MaxValue or throwing.

One could argue that Range(r).Select(i => xs.ElementAt(i)).SequenceEqual(xs.ElementsIn(r)) should be an identity (modulo side-effects of repeated enumeration due to ElementAt), thus values relative to int.MaxValue would not make sense to be treated as indexes passed to ElementAt (i.e. the view where an enumeration of a range yields valid indexes, which it can't do for "from end" indexes if the length of the source is unknown, as is the case for arbitrary IEnumerable<T> objects). That'd also cement ElementsIn (or maybe Slice if that's a better name) behavior of throwing exceptions on range violations (rather than yielding an empty sequence).

Queryable methods

Symmetry makes sense to me; there's been a precedent of extending the surface with TakeLast and SkipLast. However, two possible concerns could be:

• Query providers may break in a variety of ways because they see new overloads to ElementAt[OrDefault]. E.g. they could use reflection to get MethodInfo for these, under the assumption there's only a single overload (e.g. short-sighted use of Single or [0]). Or, they could match simply on name and try to interpret the second argument as Int32 and fail there. Note this is different from TakeLast and SkipLast which were brand new names.
• Query providers could freak out seeing Index or Range objects appear in an expression tree. I'm also not sure on the plan of record for using .. in lambda expressions converted to expression trees; either these would become MethodCallExpression nodes to factory methods (as is the case for $"..." interpolated strings using string.Format), or get rejected by the C# compiler (as is the case for e.g. ?.).

One could argue different ways here:

• .NET Core supports side-by-side, so this type of compat is less of a concern today. We could also make sure that LINQ to SQL and Entity Framework are not affected.
• We can't run the risk, and
  
  
  
  • asymmetry is tolerable (which makes me cringe);
  
  
  • we can put it in another library (thus on another EnumerableExtensions method, reducing the risk of query providers blowing up; though if they just check method names, they'd still be in trouble).
  
  

For the very last (personally not preferred, to be clear) option, note that the query provider supporting AsQueryable on an IEnumerable<T> is happy to find an IEnumerable<T>-based method on the same declaring type for purposes of rebinding IQueryable<T>-based methods to their "local" equivalent (see https://github.com/dotnet/corefx/blob/master/src/System.Linq.Queryable/src/System/Linq/EnumerableRewriter.cs#L49), so the symmetry can be kept in an extension library (such as Ix).

One data point for this decision could be the proposed addition of a Zip method with a ValueTuple return type, see https://github.com/dotnet/corefx/issues/16011. This is analogous in two ways: reuse of the same method name, and occurrence of a new type in expression trees (though not in an operator argument position, but in the return type, so typically treated differently by query providers).

[Clockwork-Muse]

In light of symmetry, don't forget PLINQ (where operators must be implemented by the library, and not with add-ons).

[Dixin]

@bartdesmet Thank you for your insights. I hope these LINQ operators can be provided in corefx. Since index/range are language level features, it is nice to have them work with not only array, but also any type that implements IEnumerable<T>.

[Dixin]

@Clockwork-Muse I looked at PLINQ before I post this proposal. ParallelEnumerable is not symmetric with Enumerable/Queryable. Enumerable/Queryable have Append/Prepend/SkipLast/TakeLast operators but ParallelEnumerable does not have them.

[Clockwork-Muse]

@Dixin -
That's fine, if you've already reviewed it and decided not to include it.

[joshfree]

@tarekgh

[Dixin]

@joshfree @tarekgh Thank you for labeling this issue. Since it is now in the Future Milestone (issues not triaged to a planned release. Work in this milestone may happen, or may not). Does it mean there is not much chance of actions for the next release? Please suggest what should I do next.

[tarekgh]

Does it mean there is not much chance of actions for the next release? Please suggest what should I do next.

We'll look at the details to ensure the proposed APIs is reasonable and then we'll have the issue reviewed by the design committee. expect will get traction on this when we ship 3.0. if you didn't see any activities by then, please ping us. Usually we'll get into that in right time. Thanks for the proposal.

[Dixin]

Thank you @tarekgh.