www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Input ranges do not compose

reply Sergey Gromov <snake.scaly gmail.com> writes:
Say I want to present a file as an input range:

class RangeFile {
     bool empty() {...}
     ubyte front() {...}
     void popFront() {...}
     // some private stuff
}

I'm parsing it.  There are chunks, one byte for size then data of that size:

void parse(RangeFile rf) {
     while (!rf.empty) {
         int size = rf.front;
         rf.popFront();
         popFrontN(rf, size);
     }
}

It works.  Now let's do something useful with the chunks' contents. 
There are strings in there, byte for length, then that much characters. 
  Read 'em:

void parse(RangeFile rf) {
     while (!rf.empty) {
         int size = rf.front;
         rf.popFront();
         auto chunk = take(size, rf);
         while (!chunk.empty) {
             int len = chunk.front;
             chunk.popFront();
             auto str = new char[len];
             copy(take(len, chunk), str);
         }
     }
}

BANG.  This does not work.  The chunk won't end where it should.  The 
problem is that second take() creates a copy of the chunk data, and the 
copy() does not update chunk's remaining size while copying.

This behavior is fine and expected and desired for forward ranges and up 
but makes no sense for input ranges.

I thought I could fix it rewriting copy:

copy(take(len, &chunk), str);

But it didn't compile.  Told me something about something not being lvalue.

There are actually two issues:

1.  Most of the std.algorithm and std.range functions claim that they 
accept input ranges but take them *by value*.  This violates input 
ranges' non-copyable contract.

2.  A whole bunch of algorithms is required similar to those we have now 
but accepting their range arguments by reference and mutating them.

Do I miss something?  The ranges do not seem as universal to me anymore.
Dec 02 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Sergey Gromov wrote:

 Say I want to present a file as an input range:
 
 class RangeFile {
     bool empty() {...}
     ubyte front() {...}
     void popFront() {...}
     // some private stuff
 }
 
 I'm parsing it.  There are chunks, one byte for size then data of that 
 size:
 
 void parse(RangeFile rf) {
     while (!rf.empty) {
         int size = rf.front;
         rf.popFront();
         popFrontN(rf, size);
     }
 }
 
 It works.  Now let's do something useful with the chunks' contents. 
 There are strings in there, byte for length, then that much characters. 
  Read 'em:
 
 void parse(RangeFile rf) {
     while (!rf.empty) {
         int size = rf.front;
         rf.popFront();
         auto chunk = take(size, rf);
         while (!chunk.empty) {
             int len = chunk.front;
             chunk.popFront();
             auto str = new char[len];
             copy(take(len, chunk), str);
         }
     }
 }
 
 BANG.  This does not work.  The chunk won't end where it should.  The 
 problem is that second take() creates a copy of the chunk data, and the 
 copy() does not update chunk's remaining size while copying.
 
 This behavior is fine and expected and desired for forward ranges and up 
 but makes no sense for input ranges.
 
 I thought I could fix it rewriting copy:
 
 copy(take(len, &chunk), str);
 
 But it didn't compile.  Told me something about something not being lvalue.
 
 There are actually two issues:
 
 1.  Most of the std.algorithm and std.range functions claim that they 
 accept input ranges but take them *by value*.  This violates input 
 ranges' non-copyable contract.
 
 2.  A whole bunch of algorithms is required similar to those we have now 
 but accepting their range arguments by reference and mutating them.
 
 Do I miss something?  The ranges do not seem as universal to me anymore.


This issue is solved by save(), see 
http://erdani.com/publications/on-iteration.html. We need to make one 
more pass through the ranges and the range-related stuff in Phobos to 
use save().

Andrei
Dec 02 2009
parent Sergey Gromov <snake.scaly gmail.com> writes:
Andrei Alexandrescu wrote:

 Sergey Gromov wrote:

 There are actually two issues:

 1.  Most of the std.algorithm and std.range functions claim that they 
 accept input ranges but take them *by value*.  This violates input 
 ranges' non-copyable contract.

 2.  A whole bunch of algorithms is required similar to those we have 
 now but accepting their range arguments by reference and mutating them.

 Do I miss something?  The ranges do not seem as universal to me anymore.


 
 This issue is solved by save(), see 
 http://erdani.com/publications/on-iteration.html. We need to make one 
 more pass through the ranges and the range-related stuff in Phobos to 
 use save().


Thinking about it, save() can save the day if all the range manipulation 
functions are changed to receive ranges by reference and to keep value 
ranges by pointer internally, and use save() if they really want a copy. 
  Otherwise, if take() still returns Take!() value and copy() still 
receives it by value, save() won't change anything.
Dec 02 2009