ideas about ranges

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> 
> The thread discussing what to do for input ranges vs. forward ranges got 
> me thinking.
> 
> The range concept may be defined backwards in terms of which is more 
> specialized.  Consider that an input range is always usable as a 
> stream.  But a stream is not easy to use as an input range (the range 
> primitive).

The hierarchy of concepts is:

input range < forward range < bidirectional range < random-access range

Having length, having slicing, and infinity are orthogonal properties.

> Case in point, a file.  To fit into the most primitive range concept, it 
> must define 3 functions:
> 
> front()
> popFront()
> empty()
> 
> empty is easy, it's just "am I at end of file"
> 
> But front is not so easy.  In order to know what's at the front, you 
> need to read it.  And at that point you've altered the underlying file.

Not even empty is easy. If you're defining a file range that gives you 
e.g. whitespace-separated integers, you can't have empty return feof(p) 
because there might be only spaces through the end of file. So you need 
to cache one element ahead to be able to implement empty().

I've discussed this with Walter for the longest time. The correct 
primitive for an input range that needs to do no caching is:

Tuple!(T, "data", bool, "got") popNext();

When you call popNext it decides in the same place whether there is 
data, and also gives it to you. If "got" comes off as false, you know 
you're done.

There are two issues with this form. It's not easy to use (even if you 
play around with the signature by e.g. passing data or bool by 
reference) and it's not easy to inline for non-input ranges. The second 
problem could possibly be eliminated, but the first stays. It's just too 
clunky a primitive to use, you'll need temporaries and all that stuff.

> Look at the implementation of front and popFront for a possible 
> FileByChar implementation:
> 
> dchar front()
> {
>   if(!bufferValid)
>     popFront();
>   return buffer;
> }
> 
> void popFront()
> {
>    // read buffer from source, setting bufferValid if the range isn't 
> empty by default
> }
> 
> What sucks about this is, we have to introduce a buffer in the range, 
> just because we can't look at data until we've popped it.  Not only 
> that, but calling front a file before anything is read requires a check 
> to fill the buffer in case we haven't read anything yet.  This could be 
> alleviated by filling in the constructor, but it's still more complex 
> than necessary.  Consider also that the underlying stream might already 
> be buffered, so we are buffering a buffer.

Yah, I agree. I've implemented a few of those in Phobos. It would be 
good to have a more solid solution. This problem, however, also collides 
with returning an rvalue versus a ref. A container wants to return a 
ref. An input range wants to return by value. Then it's difficult to use 
a container as an input range.

> And finally, if you copy such a range, the buffer might be copied while 
> the stream itself may not.  this could result in strange garbage data.

I don't understand this. You could make sure copy does the right thing.

> But since the primitives for input range are set by the compiler (it 
> uses them to do foreach), we have to implement them to make our stream 
> ranges friendly to foreach.
> 
> Round peg, meet square hole.
> 
> But what are the true requirements for iteration using foreach?
> 
> 1. check if there's anything left
> 2. get the next element
> 
> Step 2 now is split into popFront and front.  So a foreach loop is a 
> rewritten for loop like this:
> 
> foreach(x; range)
> {
>   ...
> }
> 
> translates to:
> {
>   auto _r = range;
>   while(!_r.empty)
>   {
>     auto x = _r.front();
>     _r.popFront();
>     ...
>   }
> }
> 
> What if step 2 was one function?  Call it popNext(), and make it 
> equivalent to calling _r.front() and popFront() in one step on ranges 
> that implement that method.

This will not solve all problems. It will improve things like defining 
ranges that read one character at a time from a stream. But a function 
that does read-and-check-for-empty in one shot is the true solution.

> How does this work with foreach?
> 
> {
>   auto _r = range;
>   while(!_r.empty)
>   {
>     auto x = _r.popNext();
>     ...
>   }
> }
> 
> Basically, the same code, one less line.
> 
> Consider that any range defined today with front() and popFront() can 
> implement popNext (and popNext could be an external function if we can 
> get 3015 resolved).
> 
> So what I think we may need is a different range primitive:
> 
> An iterable range defines: (name to be decided)
> 
> bool empty()
> T popNext()
> 
> An input range is an iterable range that also defines:
> 
> T front();
> popFront();

I think you are using "iterable range" instead of "input range" and 
"input range" instead of "forward range". This is compared to STL 
terminology, which I borrowed.

> Now look at our FileByChar example as an iterable range:
> 
> T popNext()
> {
>    return source.get(); // no buffering required
> }
> 
> And it works perfectly with the new foreach requirements.
> 
> And it correctly doesn't work with algorithms that require front and 
> popFront.

That's great. Again, popNext integrated with check for empty is the best 
solution. The correct way to go is to define this:

T popNext(ref bool gotSomething);

and leave it to the discretion of the range if they prefer returning by 
reference:

ref T popNext(ref bool gotSomething);

(this might be good for many forward ranges.) Then we nicely ask Walter 
to allow inlining of such functions, and finally implement this in 
std.range:

ref ElementType!R popNext(R)(R r, ref bool gotSomething)
     if (isForwardRange!R)
{
     if (r.empty)
     {
         gotSomething = false;
         static typeof(return) dumbo;
         return dumbo;
     }
     auto result = &(r.front());
     r.popFront();
     gotSomething = true;
     return *result;
}

Admittedly this looks considerably messier than it ought to, and that's 
never a good sign. For starters, I could predict with accuracy the 
sneering remarks of certain posters who shall remain unnamed. Worse, 
they'd have a point (only) this one time :o). Messiness was one of the 
factors that made me decide to steer away from this design. A simpler 
solution is to just return by value:

ElementType!R popNext(R)(R r, ref bool gotSomething)
     if (isForwardRange!R)
{
     if (r.empty)
     {
         gotSomething = false;
         return typeof(return).init;
     }
     auto result = r.front;
     r.popFront();
     return result;
}

This looks a tad more sane. But then it copies data more than it 
strictly should, and for whom? For everything that's not strictly a file 
input, which is most things you want to iterate! Wrong default.

As of this time, I am undecided on what's the best way to go. Opinions 
are welcome.


Andrei