www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - std.range.interfaces : InputRange moveFront

reply Tony <tonytdominguez aol.com> writes:
What does the moveFront() method do in the InputRange interface?

std.range.interfaces : InputRange.moveFront()
Nov 29 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/29/2017 08:31 PM, Tony wrote:

 What does the moveFront() method do in the InputRange interface?
 
 std.range.interfaces : InputRange.moveFront()


move is an operation that transfers the state of the source to the 
destination. The front element becomes its .init value and its previous 
values is returned by moveFront().

The important bit is that, the element is *not* copied:

import std.range;

struct S {
     int i;
     bool is_a_copy = false;
     this(this) {
         is_a_copy = true;
     }
}

void main() {
     auto r =  [S(1)];

     auto a = r.front;
     assert(a.is_a_copy);       // yes, a is a copy
     assert(a.i == 1);          // as expected, 1
     assert(r.front.i == 1);    // front is still 1

     auto b = r.moveFront();
     assert(!b.is_a_copy);      // no, b is not a copy
     assert(b.i == 1);          // state is transferred
     assert(r.front.i == 0);    // front is int.init
}

Ali
Nov 29 2017
next sibling parent reply Tony <tonytdominguez aol.com> writes:
On Thursday, 30 November 2017 at 06:36:12 UTC, Ali Çehreli wrote:


 move is an operation that transfers the state of the source to 
 the destination. The front element becomes its .init value and 
 its previous values is returned by moveFront().

 The important bit is that, the element is *not* copied:

 import std.range;

 struct S {
     int i;
     bool is_a_copy = false;
     this(this) {
         is_a_copy = true;
     }
 }

 void main() {
     auto r =  [S(1)];

     auto a = r.front;
     assert(a.is_a_copy);       // yes, a is a copy
     assert(a.i == 1);          // as expected, 1
     assert(r.front.i == 1);    // front is still 1

     auto b = r.moveFront();
     assert(!b.is_a_copy);      // no, b is not a copy
     assert(b.i == 1);          // state is transferred
     assert(r.front.i == 0);    // front is int.init
 }


Thanks for the reply. Probably just missing it, but in poking 
around dlang.org (Language Reference and Library Reference) I am 
having trouble finding out about the move(), front() and 
moveFront() functions, as is used here on a dynamic array.
Nov 30 2017
parent reply Tony <tonytdominguez aol.com> writes:
On Thursday, 30 November 2017 at 09:47:14 UTC, Tony wrote:


 Thanks for the reply. Probably just missing it, but in poking 
 around dlang.org (Language Reference and Library Reference) I 
 am having trouble finding out about the move(), front() and 
 moveFront() functions, as is used here on a dynamic array.


That should just be front() and moveFront() used here. I ran 
across move() in looking at the standard library for the 
definitions of the other two.
Nov 30 2017
parent reply Tony <tonytdominguez aol.com> writes:
On Thursday, 30 November 2017 at 09:50:37 UTC, Tony wrote:

 On Thursday, 30 November 2017 at 09:47:14 UTC, Tony wrote:


 Thanks for the reply. Probably just missing it, but in poking 
 around dlang.org (Language Reference and Library Reference) I 
 am having trouble finding out about the move(), front() and 
 moveFront() functions, as is used here on a dynamic array.


 That should just be front() and moveFront() used here. I ran 
 across move() in looking at the standard library for the 
 definitions of the other two.


Found a move() here:
https://dlang.org/library/std/algorithm/mutation/move.html
Function std.algorithm.mutation.move
Nov 30 2017
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/30/2017 07:31 AM, Tony wrote:

 On Thursday, 30 November 2017 at 09:50:37 UTC, Tony wrote:

 On Thursday, 30 November 2017 at 09:47:14 UTC, Tony wrote:


 Thanks for the reply. Probably just missing it, but in poking around 
 dlang.org (Language Reference and Library Reference) I am having 
 trouble finding out about the move(), front() and moveFront() 
 functions, as is used here on a dynamic array.


 That should just be front() and moveFront() used here. I ran across 
 move() in looking at the standard library for the definitions of the 
 other two.


 
 Found a move() here:
 https://dlang.org/library/std/algorithm/mutation/move.html
 Function std.algorithm.mutation.move


I don't know why it isn't listed at the top of the page but front() for 
arrays is here:

   https://dlang.org/phobos/std_range_primitives.html#.front

And moveFront():

   https://dlang.org/phobos/std_range_primitives.html#.moveFront

Ali
Nov 30 2017
prev sibling parent reply Johan Engelen <j j.nl> writes:
On Thursday, 30 November 2017 at 06:36:12 UTC, Ali Çehreli wrote:

 import std.range;

 struct S {
     int i;
     bool is_a_copy = false;
     this(this) {
         is_a_copy = true;
     }
 }

 void main() {
     auto r =  [S(1)];

     auto a = r.front;
     assert(a.is_a_copy);       // yes, a is a copy
     assert(a.i == 1);          // as expected, 1
     assert(r.front.i == 1);    // front is still 1

     auto b = r.moveFront();
     assert(!b.is_a_copy);      // no, b is not a copy
     assert(b.i == 1);          // state is transferred
     assert(r.front.i == 0);    // front is int.init
 }


I tested it and it works like you wrote, but the behavior is 
different for an array of integers...:

auto a = [ 1,2,3 ];
writeln(a.front); // 1
auto b = a.moveFront();
writeln(b); // 1
writeln(a.length); // still 3
writeln(a.front); // still 1

-Johan
Dec 01 2017
next sibling parent reply Johan Engelen <j j.nl> writes:
On Friday, 1 December 2017 at 09:11:40 UTC, Johan Engelen wrote:

 I tested it and it works like you wrote, but the behavior is 
 different for an array of integers...:


Hmm, I guess I misread what Ali meant. But the documentation is 
wrong/very confusing for moveFront:
It says "moveFront -- Removes the front element of a range." and 
"Moves the front of r out and returns it."  With "to move _out_", 
I would expect that the range is advanced/shortened/..., but it 
is not.

(Also, I would expect "popFront" to return the element popped, 
but it doesn't, OK...
So which function name is given to the behavior of "pop" of other 
languages?)

-Johan
Dec 01 2017
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/1/17 4:29 AM, Johan Engelen wrote:

 On Friday, 1 December 2017 at 09:11:40 UTC, Johan Engelen wrote:

 I tested it and it works like you wrote, but the behavior is different 
 for an array of integers...:


 
 Hmm, I guess I misread what Ali meant. But the documentation is 
 wrong/very confusing for moveFront:
 It says "moveFront -- Removes the front element of a range." and "Moves 
 the front of r out and returns it."  With "to move _out_", I would 
 expect that the range is advanced/shortened/..., but it is not.


move is supposed to move the bits from one place to another (i.e. 
without calling any constructor or postblit). It doesn't destroy the 
existence of the original, it's supposed to leave it as an empty shell 
(read: set the original to it's .init value).

However, I'm surprised the front element is still 1. I would think it 
should be int.init. But I guess it makes sense that if a type doesn't 
have a destructor, there's no need to worry about initializing it. move 
probably doesn't care if it's a value type without a destructor.


 (Also, I would expect "popFront" to return the element popped, but it 
 doesn't, OK...


pop removes the front element, but if getting the front element is 
expensive (say if it's a map with a complex lambda function), you don't 
want to execute that just so you can return it to someone who doesn't 
care. This is why front and popFront are separate.


 So which function name is given to the behavior of "pop" of other 
 languages?)


Nothing. You have to do both front and popFront. Others have proposed a 
wrapper that does both, but in order to truly take advantage of the fact 
that you are removing and calculating the front value at the same time, 
you need a new range type. Some have suggested that too.

-Steve
Dec 01 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:

 On 12/1/17 4:29 AM, Johan Engelen wrote:



 (Also, I would expect "popFront" to return the element popped, but it
 doesn't, OK...


 pop removes the front element, but if getting the front element is
 expensive (say if it's a map with a complex lambda function), you don't
 want to execute that just so you can return it to someone who doesn't
 care. This is why front and popFront are separate.


Yet, we're told that compilers are pretty good at eliminating that 
unused copy especially for function templates where all code is visible.

[I have second thoughts about what I write below. Bear with me...]

I think the actual reason is one that I learned in C++ circles which I 
will never forget as I was lurking on comp.lang.c++.moderated as the 
whole exception safety was discussed, finally solved, and popularized by 
Herb Sutter.

So, even thoug exception safety is not a common topic of D community, 
the real reason for why popFront() does not return the element is for 
strong exception safety guarantee. Otherwise, it's not possible to 
recover from a post-blit that may throw. The reason is, popFront() must 
change the structure of the container *before* the returned object must 
be copied. When the copying throws, then the element is already lost 
from the container.

However, there are two potential solutions that I think of:

- D could move the element out; so no post-blit would be necessary. 
However, as we see in moveFront()'s source code, it might have to call a 
provided moveFront() and that might throw:

     static if (is(typeof(&r.moveFront)))
     {
         return r.moveFront();
     }

- D has scope(failure) which could revert the container's state but I 
don't think it's possible for all containers. (And I should have said 
"ranges".)

Regardless, separating front() from popFront() is preferable due to 
cohesion: fewer responsibilities per function, especially such low level 
ones.

Ali
Dec 01 2017
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/1/17 1:33 PM, Ali Çehreli wrote:

 On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:
  > On 12/1/17 4:29 AM, Johan Engelen wrote:
 
  >> (Also, I would expect "popFront" to return the element popped, but it
  >> doesn't, OK...
  >
  > pop removes the front element, but if getting the front element is
  > expensive (say if it's a map with a complex lambda function), you don't
  > want to execute that just so you can return it to someone who doesn't
  > care. This is why front and popFront are separate.
 
 Yet, we're told that compilers are pretty good at eliminating that 
 unused copy especially for function templates where all code is visible.


yes, true. But this is not something to rely on, and it's not always 
possible.


 [I have second thoughts about what I write below. Bear with me...]
 
 I think the actual reason is one that I learned in C++ circles which I 
 will never forget as I was lurking on comp.lang.c++.moderated as the 
 whole exception safety was discussed, finally solved, and popularized by 
 Herb Sutter.
 
 So, even thoug exception safety is not a common topic of D community, 
 the real reason for why popFront() does not return the element is for 
 strong exception safety guarantee. Otherwise, it's not possible to 
 recover from a post-blit that may throw. The reason is, popFront() must 
 change the structure of the container *before* the returned object must 
 be copied. When the copying throws, then the element is already lost 
 from the container.


Hm... yes this is a more pressing problem. But I don't know if it has to 
do with exception safety vs. purely implementation concerns. I remember 
discussions about such a wrapper, and a case where it breaks down is byLine.

Once you popFront a byLine range, the element that was at front is now 
possibly invalid (the buffer may be reused). So in order to return the 
line from popFront, you have to store it somewhere. This means 
allocating another buffer to hold the line you just returned. So the 
costs of doing this aren't just that you might do work and just throw it 
away, it's that you have this extra caching problem you didn't have before.


 However, there are two potential solutions that I think of:
 
 - D could move the element out; so no post-blit would be necessary. 
 However, as we see in moveFront()'s source code, it might have to call a 
 provided moveFront() and that might throw:
 
      static if (is(typeof(&r.moveFront)))
      {
          return r.moveFront();
      }


For byLine, this is a non-starter. You can't move the whole thing into 
the return value, as it's referenced data. You'd have to allocate.


 - D has scope(failure) which could revert the container's state but I 
 don't think it's possible for all containers. (And I should have said 
 "ranges".)


Most definitely, ranges never expand.

-Steve
Dec 01 2017
parent Johan Engelen <j j.nl> writes:
On Friday, 1 December 2017 at 18:55:53 UTC, Steven Schveighoffer 
wrote:

 Once you popFront a byLine range, the element that was at front 
 is now possibly invalid (the buffer may be reused). So in order 
 to return the line from popFront, you have to store it 
 somewhere. This means allocating another buffer to hold the 
 line you just returned. So the costs of doing this aren't just 
 that you might do work and just throw it away, it's that you 
 have this extra caching problem you didn't have before.


Cool, thanks.
Can we add points like this to the documentation?
(if not, user frustration and forum threads will keep coming 
about these things... ;-)

-Johan
Dec 02 2017
prev sibling parent reply Johan Engelen <j j.nl> writes:
On Friday, 1 December 2017 at 18:33:09 UTC, Ali Çehreli wrote:

 On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:

 On 12/1/17 4:29 AM, Johan Engelen wrote:



 (Also, I would expect "popFront" to return the element




 popped, but it

 doesn't, OK...


 pop removes the front element, but if getting the front


 element is

 expensive (say if it's a map with a complex lambda function),


 you don't

 want to execute that just so you can return it to someone who


 doesn't

 care. This is why front and popFront are separate.


 Yet, we're told that compilers are pretty good at eliminating 
 that unused copy especially for function templates where all 
 code is visible.


I assume that Steven means "copying the front element" when he 
wrote "getting the front element"? There is no need for a copy, 
because the element will be removed from the range, so we can 
move (whose cost only depends on the size of the element, 
internal pointers being disallowed by the language).
If it is expensive to actually get _to_ the front/back element 
(i.e. find its memory location), then having to do the operation 
twice is a disadvantage.

Ali: the compiler can only elide copying/moving of an unused 
return value when inlining the function. (the duty of making the 
return value move/copy is on the callee, not the caller)

Note that because front/back() and popFront/Back() are separate, 
a copy *is* needed when one wants to "pop an element off". Thus 
moveFront/Back() and popFront/Back() should be used. OK.
The fact that "pop" does something different from other 
programming languages is something important to remember when 
teaching people about D. And I think should be made clear in the 
documentation; let's add an example of how one is supposed to use 
all this in an efficient manner?

Back on topic: let's change the documentation of moveFront such 
that it is clear that it does _not_ reduce the number of elements 
in the range?


 So, even though exception safety is not a common topic of D 
 community, the real reason for why popFront() does not return 
 the element is for strong exception safety guarantee.


Interesting point. Argh why do we allow the user to throw in move?


 Regardless, separating front() from popFront() is preferable 
 due to cohesion: fewer responsibilities per function, 
 especially such low level ones.


This doesn't make much sense ;-)
popFrontN has more responsibility, and one gains better 
performance than simply calling popFront N times. It's similar 
here.

-Johan
Dec 02 2017
next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/3/17 12:42 AM, Johan Engelen wrote:

 On Friday, 1 December 2017 at 18:33:09 UTC, Ali Çehreli wrote:

 On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:

 On 12/1/17 4:29 AM, Johan Engelen wrote:



 (Also, I would expect "popFront" to return the element




 popped, but it

 doesn't, OK...


 pop removes the front element, but if getting the front


 element is

 expensive (say if it's a map with a complex lambda function),


 you don't

 want to execute that just so you can return it to someone who


 doesn't

 care. This is why front and popFront are separate.


 Yet, we're told that compilers are pretty good at eliminating that 
 unused copy especially for function templates where all code is visible.


 
 I assume that Steven means "copying the front element" when he wrote 
 "getting the front element"?


No I mean generating the front element. For example:

auto m = [1, 2, 3].map!(a => reallyExpensiveFunction(a));

Each time you call front, it's going to be really expensive. If you 
aren't going to use it, then generating it is wasted cycles.

(BTW, I said "pop" when I meant "popFront", sorry for *that* confusion too!)


 There is no need for a copy, because the 
 element will be removed from the range, so we can move (whose cost only 
 depends on the size of the element, internal pointers being disallowed 
 by the language).


Yeah, this wasn't my concern, sorry for being ambiguous.

-Steve
Dec 04 2017
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/03/2017 12:42 AM, Johan Engelen wrote:

 On Friday, 1 December 2017 at 18:33:09 UTC, Ali Çehreli wrote:

 On 12/01/2017 07:21 AM, Steven Schveighoffer wrote:

 On 12/1/17 4:29 AM, Johan Engelen wrote:



 (Also, I would expect "popFront" to return the element




 popped, but it

 doesn't, OK...


 pop removes the front element, but if getting the front


 element is

 expensive (say if it's a map with a complex lambda function),


 you don't

 want to execute that just so you can return it to someone who


 doesn't

 care. This is why front and popFront are separate.


 Yet, we're told that compilers are pretty good at eliminating that 
 unused copy especially for function templates where all code is visible.


 
 I assume that Steven means "copying the front element" when he wrote 
 "getting the front element"? There is no need for a copy, because the 
 element will be removed from the range, so we can move (whose cost only 
 depends on the size of the element, internal pointers being disallowed 
 by the language).
 If it is expensive to actually get _to_ the front/back element (i.e. 
 find its memory location), then having to do the operation twice is a 
 disadvantage.
 
 Ali: the compiler can only elide copying/moving of an unused return 
 value when inlining the function. (the duty of making the return value 
 move/copy is on the callee, not the caller)
 
 Note that because front/back() and popFront/Back() are separate, a copy 
 *is* needed when one wants to "pop an element off". Thus 
 moveFront/Back() and popFront/Back() should be used. OK.
 The fact that "pop" does something different from other programming 
 languages is something important to remember when teaching people about 
 D. And I think should be made clear in the documentation; let's add an 
 example of how one is supposed to use all this in an efficient manner?
 
 Back on topic: let's change the documentation of moveFront such that it 
 is clear that it does _not_ reduce the number of elements in the range?
 

 So, even though exception safety is not a common topic of D community, 
 the real reason for why popFront() does not return the element is for 
 strong exception safety guarantee.


 
 Interesting point. Argh why do we allow the user to throw in move?
 

 Regardless, separating front() from popFront() is preferable due to 
 cohesion: fewer responsibilities per function, especially such low 
 level ones.


 
 This doesn't make much sense ;-)
 popFrontN has more responsibility, and one gains better performance than 
 simply calling popFront N times. It's similar here.


Thanks Ali for asking me to comment in this thread. The matter of fact 
is moveFront was needed for different purposes.

First off, moving in D cannot throw; all objects are moveable by means 
of bitwise move.

The main reason for moveFront's existence is supporting ranges that have 
front() return an rvalue. For those, there would otherwise be no 
efficient means to move data out of the range to its user.

Now, why does popFront return void instead of the popped element? We 
need front() anyway as a non-destructive way to look at the current 
element of the range, so having popFront return that element is 
redundant. Plus, it's difficult to optimize away particularly in 
separately compiled code.


Andrei
Dec 08 2017
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 12/01/2017 01:11 AM, Johan Engelen wrote:


 I tested it and it works like you wrote, but the behavior is different 
 for an array of integers...:
 
 auto a = [ 1,2,3 ];
 writeln(a.front); // 1
 auto b = a.moveFront();
 writeln(b); // 1
 writeln(a.length); // still 3
 writeln(a.front); // still 1
 
 -Johan


Good catch, which affects my struct S example as well.

It's a documentation bug as it does not mention different behavior 
depending on elaborate copy constructor:

   https://github.com/dlang/phobos/blob/master/std/range/primitives.d#L1848

ElementType!R moveFront(R)(R r)
{
     static if (is(typeof(&r.moveFront)))
     {
         return r.moveFront();
     }
     else static if (!hasElaborateCopyConstructor!(ElementType!R))
     {
         return r.front;
     }
     else static if (is(typeof(&(r.front())) == ElementType!R*))
     {
         import std.algorithm.mutation : move;
         return move(r.front);
     }
     else
     {
         static assert(0,
                 "Cannot move front of a range with a postblit and an 
rvalue front.");
     }
}

Ali
Dec 01 2017