Below is a simple implementation of a range which iterates another (input) range by reference, for those cases when using an InputRangeObject is overkill.  I've used it quite a bit and I find it immensely useful.

It is sort of the opposite of save().  Where save() ensures that you are
only consuming a copy of the original range, byRef() ensures that you
are consuming the original range.

Would this be useful for Phobos?  I guess it is a tad unsafe, since it stores the address of the range, which may well be stored on the stack.


/** Range that iterates another range by reference. */
auto byRef(Range)(ref Range range) if (isInputRange!Range)
{
    static struct ByRef
    {
        private Range* _range;

        static if (isInfinite!Range)
        {
            enum empty = false;
        }
        else
        {
            @property bool empty() { return (*_range).empty; }
        }

        @property ElementType!Range front()
        {
            return (*_range).front;
        }

        void popFront()
        {
            (*_range).popFront();
        }
    }

    return ByRef(&range);
}

unittest
{
    auto a = [1, 2, 3, 4];
    auto b = take(byRef(a), 2);

    assert (equal(b, [1, 2]));
    assert (equal(a, [3, 4]));
}


-Lars

I think the idea is interesting.  With regard to safety, I'd recommend that byRef() just take a pointer instead of a ref parameter.  This way, if the address of a stack variable is being taken, it's explicit from the client's side and byRange is only as unsafe as the client's usage of it.

On Thu, May 19, 2011 at 10:14 AM, Lars Tandle Kyllingstad < lars at kyllingen.net> wrote:

> Below is a simple implementation of a range which iterates another (input) range by reference, for those cases when using an InputRangeObject is overkill.  I've used it quite a bit and I find it immensely useful.
>
> It is sort of the opposite of save().  Where save() ensures that you are
> only consuming a copy of the original range, byRef() ensures that you
> are consuming the original range.
>
> Would this be useful for Phobos?  I guess it is a tad unsafe, since it stores the address of the range, which may well be stored on the stack.
>
>
> /** Range that iterates another range by reference. */
> auto byRef(Range)(ref Range range) if (isInputRange!Range)
> {
>    static struct ByRef
>    {
>        private Range* _range;
>
>        static if (isInfinite!Range)
>        {
>            enum empty = false;
>        }
>        else
>        {
>            @property bool empty() { return (*_range).empty; }
>        }
>
>        @property ElementType!Range front()
>        {
>            return (*_range).front;
>        }
>
>        void popFront()
>        {
>            (*_range).popFront();
>        }
>    }
>
>    return ByRef(&range);
> }
>
> unittest
> {
>    auto a = [1, 2, 3, 4];
>    auto b = take(byRef(a), 2);
>
>    assert (equal(b, [1, 2]));
>    assert (equal(a, [3, 4]));
> }
>
>
> -Lars
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20110519/8e007adf/attachment.html>

On Thu, 19 May 2011 10:14:58 -0400, Lars Tandle Kyllingstad <lars at kyllingen.net> wrote:
> Below is a simple implementation of a range which iterates another (input) range by reference, for those cases when using an InputRangeObject is overkill.  I've used it quite a bit and I find it immensely useful.
>
> It is sort of the opposite of save().  Where save() ensures that you are
> only consuming a copy of the original range, byRef() ensures that you
> are consuming the original range.
>
> Would this be useful for Phobos?  I guess it is a tad unsafe, since it stores the address of the range, which may well be stored on the stack.
>
>
> /** Range that iterates another range by reference. */
> auto byRef(Range)(ref Range range) if (isInputRange!Range)
> {
>     static struct ByRef
>     {
>         private Range* _range;
>
>         static if (isInfinite!Range)
>         {
>             enum empty = false;
>         }
>         else
>         {
>             @property bool empty() { return (*_range).empty; }
>         }
>
>         @property ElementType!Range front()
>         {
>             return (*_range).front;
>         }
>
>         void popFront()
>         {
>             (*_range).popFront();
>         }
>     }
>
>     return ByRef(&range);
> }
>
> unittest
> {
>     auto a = [1, 2, 3, 4];
>     auto b = take(byRef(a), 2);
>
>     assert (equal(b, [1, 2]));
>     assert (equal(a, [3, 4]));
> }

I've wrote version of this for my Json library, so yes, I think it's useful. I'd recommend a few things. First, if the Range is a reference type, then you don't need the extra level of indirection. Second, you may wish to include the rest of the range primitives, plus length/slicing, if the base type supports them.

On Thu, 2011-05-19 at 14:24 -0400, Robert Jacques wrote:
> On Thu, 19 May 2011 10:14:58 -0400, Lars Tandle Kyllingstad <lars at kyllingen.net> wrote:
> > Below is a simple implementation of a range which iterates another (input) range by reference, for those cases when using an InputRangeObject is overkill.  I've used it quite a bit and I find it immensely useful.
> >
> > It is sort of the opposite of save().  Where save() ensures that you are
> > only consuming a copy of the original range, byRef() ensures that you
> > are consuming the original range.
> >
> > Would this be useful for Phobos?  I guess it is a tad unsafe, since it stores the address of the range, which may well be stored on the stack.
> >
> >
> > /** Range that iterates another range by reference. */
> > auto byRef(Range)(ref Range range) if (isInputRange!Range)
> > {
> >     static struct ByRef
> >     {
> >         private Range* _range;
> >
> >         static if (isInfinite!Range)
> >         {
> >             enum empty = false;
> >         }
> >         else
> >         {
> >             @property bool empty() { return (*_range).empty; }
> >         }
> >
> >         @property ElementType!Range front()
> >         {
> >             return (*_range).front;
> >         }
> >
> >         void popFront()
> >         {
> >             (*_range).popFront();
> >         }
> >     }
> >
> >     return ByRef(&range);
> > }
> >
> > unittest
> > {
> >     auto a = [1, 2, 3, 4];
> >     auto b = take(byRef(a), 2);
> >
> >     assert (equal(b, [1, 2]));
> >     assert (equal(a, [3, 4]));
> > }
> 
> I've wrote version of this for my Json library, so yes, I think it's useful. I'd recommend a few things. First, if the Range is a reference type, then you don't need the extra level of indirection. Second, you may wish to include the rest of the range primitives, plus length/slicing, if the base type supports them.

It definitely needs to be fleshed out a bit, yes.  Right now it's sufficient for my uses, however, so I just thought I'd gauge the interest before making any improvements.

I can't really see any elegant way to implement save() for such a range, though, and without save() it doesn't qualify as a forward range, a bidirectional range or a random-access range -- at least not as defined by isForwardRange & co.  Is there then any point in implementing the remaining primitives?

-Lars

On Thu, 19 May 2011 18:09:09 -0400, Lars Tandle Kyllingstad <lars at kyllingen.net> wrote:

> On Thu, 2011-05-19 at 14:24 -0400, Robert Jacques wrote:
>> On Thu, 19 May 2011 10:14:58 -0400, Lars Tandle Kyllingstad <lars at kyllingen.net> wrote:
>> > Below is a simple implementation of a range which iterates another (input) range by reference, for those cases when using an InputRangeObject is overkill.  I've used it quite a bit and I find it immensely useful.
>> >
>> > It is sort of the opposite of save().  Where save() ensures that you
>> are
>> > only consuming a copy of the original range, byRef() ensures that you are consuming the original range.
>> >
>> > Would this be useful for Phobos?  I guess it is a tad unsafe, since it stores the address of the range, which may well be stored on the
>> stack.
>> >
>> >
>> > /** Range that iterates another range by reference. */
>> > auto byRef(Range)(ref Range range) if (isInputRange!Range)
>> > {
>> >     static struct ByRef
>> >     {
>> >         private Range* _range;
>> >
>> >         static if (isInfinite!Range)
>> >         {
>> >             enum empty = false;
>> >         }
>> >         else
>> >         {
>> >             @property bool empty() { return (*_range).empty; }
>> >         }
>> >
>> >         @property ElementType!Range front()
>> >         {
>> >             return (*_range).front;
>> >         }
>> >
>> >         void popFront()
>> >         {
>> >             (*_range).popFront();
>> >         }
>> >     }
>> >
>> >     return ByRef(&range);
>> > }
>> >
>> > unittest
>> > {
>> >     auto a = [1, 2, 3, 4];
>> >     auto b = take(byRef(a), 2);
>> >
>> >     assert (equal(b, [1, 2]));
>> >     assert (equal(a, [3, 4]));
>> > }
>>
>> I've wrote version of this for my Json library, so yes, I think it's
>> useful. I'd recommend a few things. First, if the Range is a reference
>> type, then you don't need the extra level of indirection. Second, you
>> may
>> wish to include the rest of the range primitives, plus length/slicing,
>> if
>> the base type supports them.
>
> It definitely needs to be fleshed out a bit, yes.  Right now it's sufficient for my uses, however, so I just thought I'd gauge the interest before making any improvements.
>
> I can't really see any elegant way to implement save() for such a range, though, and without save() it doesn't qualify as a forward range, a bidirectional range or a random-access range -- at least not as defined by isForwardRange & co.  Is there then any point in implementing the remaining primitives?
>
> -Lars

Well, any routine which uses byRef internally, like I do, won't necessarily care about save, but might use indexing/slicing if available.

Besides, what's wrong with something like:

static if(/*...*/)
ByRef save()
{
	auto ptr = new Range;
	*ptr = (*_range).save;
	return byRef(ptr);
}

On 5/19/11 5:09 PM, Lars Tandle Kyllingstad wrote:
> It definitely needs to be fleshed out a bit, yes.  Right now it's sufficient for my uses, however, so I just thought I'd gauge the interest before making any improvements.

In fact byRef is a fairly general tool not limited to ranges. It could work by storing the address and implementing opDispatch to forward appropriately.

We need more evidence of its utility before making a decision.


Andrei

Sorry for not following up on this earlier, I got busy with other things and completely forgot about it.


On Thu, 2011-05-19 at 18:28 -0400, Robert Jacques wrote:
> On Thu, 19 May 2011 18:09:09 -0400, Lars Tandle Kyllingstad <lars at kyllingen.net> wrote:
> 
> > I can't really see any elegant way to implement save() for such a range, though, and without save() it doesn't qualify as a forward range, a bidirectional range or a random-access range -- at least not as defined by isForwardRange & co.  Is there then any point in implementing the remaining primitives?
> >
> > -Lars
> 
> Well, any routine which uses byRef internally, like I do, won't necessarily care about save, but might use indexing/slicing if available.
> 
> Besides, what's wrong with something like:
> 
> static if(/*...*/)
> ByRef save()
> {
> 	auto ptr = new Range;
> 	*ptr = (*_range).save;
> 	return byRef(ptr);
> }

A memory allocation hidden away in a function which is normally very cheap.  I've somehow gotten the impression that algorithms can use save() without worrying about its cost.  After all, in most cases it is simply implemented as "return this" or similar.  If it turns out that save() makes no such guarantee, I don't see a problem with the implementation you suggest.

-Lars

On 2011-06-06 02:33, Lars Tandle Kyllingstad wrote:
> Sorry for not following up on this earlier, I got busy with other things and completely forgot about it.
> 
> On Thu, 2011-05-19 at 18:28 -0400, Robert Jacques wrote:
> > On Thu, 19 May 2011 18:09:09 -0400, Lars Tandle Kyllingstad
> > 
> > <lars at kyllingen.net> wrote:
> > > I can't really see any elegant way to implement save() for such a range, though, and without save() it doesn't qualify as a forward range, a bidirectional range or a random-access range -- at least not as defined by isForwardRange & co.  Is there then any point in implementing the remaining primitives?
> > > 
> > > -Lars
> > 
> > Well, any routine which uses byRef internally, like I do, won't necessarily care about save, but might use indexing/slicing if available.
> > 
> > Besides, what's wrong with something like:
> > 
> > static if(/*...*/)
> > ByRef save()
> > {
> > 
> > 	auto ptr = new Range;
> > 	*ptr = (*_range).save;
> > 	return byRef(ptr);
> > 
> > }
> 
> A memory allocation hidden away in a function which is normally very cheap.  I've somehow gotten the impression that algorithms can use save() without worrying about its cost.  After all, in most cases it is simply implemented as "return this" or similar.  If it turns out that save() makes no such guarantee, I don't see a problem with the implementation you suggest.

That's one of the main reasons for the debate on whether postblits can/should be assumed to be cheap. If they are, then algorithms can assume that save is cheap and be coded accordingly. If they're not, then calling save potentially becomes something to be avoided whenever possible. But regardless of whether save can be assumed to be cheap, it _definitely_ has the potential to allocate memory. And if something critical to a range is on the heap, then you should definitely expect a heap allocation in save.

Unfortunately, I'm not sure where the debate on postblits and cost is. As I recall, it was pretty much decided that postblits could be assumed to be cheap, but then issues with COW and reference counting being properly possible (due to bugs in the compiler I suspect, but I don't recall all of the details) made it so that decision wasn't as firm IIRC. I think that we still have all of the move functions in ranges though, and getting rid of them was one of the main goals of assuming that postblits was cheap. So, I really don't know what the situation with all that is right now.

But yes. In general, I believe that save is assumed to be fairly cheap.

- Jonathan M Davis

On Thu, 2011-05-19 at 17:34 -0500, Andrei Alexandrescu wrote:
> On 5/19/11 5:09 PM, Lars Tandle Kyllingstad wrote:
> > It definitely needs to be fleshed out a bit, yes.  Right now it's sufficient for my uses, however, so I just thought I'd gauge the interest before making any improvements.
> 
> In fact byRef is a fairly general tool not limited to ranges. It could work by storing the address and implementing opDispatch to forward appropriately.

I agree, but it would still need to be specialised for ranges.   If nothing else, the enum-ness of empty needs to be propagated.  Also, perhaps save() should *not* be propagated -- see my reply to Robert.


> We need more evidence of its utility before making a decision.

Basically, it makes the opposite guarantee of save().  It has always bothered me that if you call a function on a range,

    doStuffWith(range);

there is a priori no way to tell whether it is going to consume the original range, or whether it will iterate over a copy of the range.  It depends on the range, and it depends on the function.  While

    doStuffWith(range.save);

guarantees the latter, we need something like

    doStuffWith(byRef(range));

to guarantee the former.  Currently, the only way to do this is to write

    doStuffWith(inputRangeObject(range));

which is massive overkill if all you want is for the original range to be consumed.

-Lars

On Mon, 2011-06-06 at 02:52 -0700, Jonathan M Davis wrote:
> On 2011-06-06 02:33, Lars Tandle Kyllingstad wrote:
> > Sorry for not following up on this earlier, I got busy with other things and completely forgot about it.
> > 
> > On Thu, 2011-05-19 at 18:28 -0400, Robert Jacques wrote:
> > > On Thu, 19 May 2011 18:09:09 -0400, Lars Tandle Kyllingstad
> > > 
> > > <lars at kyllingen.net> wrote:
> > > > I can't really see any elegant way to implement save() for such a range, though, and without save() it doesn't qualify as a forward range, a bidirectional range or a random-access range -- at least not as defined by isForwardRange & co.  Is there then any point in implementing the remaining primitives?
> > > > 
> > > > -Lars
> > > 
> > > Well, any routine which uses byRef internally, like I do, won't necessarily care about save, but might use indexing/slicing if available.
> > > 
> > > Besides, what's wrong with something like:
> > > 
> > > static if(/*...*/)
> > > ByRef save()
> > > {
> > > 
> > > 	auto ptr = new Range;
> > > 	*ptr = (*_range).save;
> > > 	return byRef(ptr);
> > > 
> > > }
> > 
> > A memory allocation hidden away in a function which is normally very cheap.  I've somehow gotten the impression that algorithms can use save() without worrying about its cost.  After all, in most cases it is simply implemented as "return this" or similar.  If it turns out that save() makes no such guarantee, I don't see a problem with the implementation you suggest.
> 
> That's one of the main reasons for the debate on whether postblits can/should be assumed to be cheap. If they are, then algorithms can assume that save is cheap and be coded accordingly. If they're not, then calling save potentially becomes something to be avoided whenever possible. But regardless of whether save can be assumed to be cheap, it _definitely_ has the potential to allocate memory. And if something critical to a range is on the heap, then you should definitely expect a heap allocation in save.
> 
> Unfortunately, I'm not sure where the debate on postblits and cost is. As I recall, it was pretty much decided that postblits could be assumed to be cheap, but then issues with COW and reference counting being properly possible (due to bugs in the compiler I suspect, but I don't recall all of the details) made it so that decision wasn't as firm IIRC. I think that we still have all of the move functions in ranges though, and getting rid of them was one of the main goals of assuming that postblits was cheap. So, I really don't know what the situation with all that is right now.
> 
> But yes. In general, I believe that save is assumed to be fairly cheap.

Ok, thanks.  That cleared things up -- at least to the extent possible. :)

-Lars