• Gary Willoughby (12/12) Jul 06 2015 How do you correctly implement a bidirectional range on a linked
• Alex Parrill (10/17) Jul 06 2015 This is why modifying a sequence while iterating over it is
• anonymous (16/28) Jul 06 2015 There's no requirement for a range to stay valid when the
• anonymous (3/6) Jul 06 2015 Looks like I messed up the URL. Here's the right one:
• Jonathan M Davis via Digitalmars-d-learn (20/24) Jul 07 2015 This is why you almost never use @trusted on templated functions. You sh...
• Gary Willoughby (2/32) Jul 07 2015 Thanks for the advice.

"Gary Willoughby" <dev nomad.so> writes:

How do you correctly implement a bidirectional range on a linked 
list?

I have a linked list implementation and I've added a range 
interface to it but after a while I've realized it not quite 
right. The problem is when I call the save method of the forward 
range interface I don't get a copy I only get another view to the 
same state. So when i remove nodes from the original list the 
range becomes invalid.

How can you implement such a range over a type whose state is 
accessed via pointers?

Here's my implementation:

https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533

"Alex Parrill" <initrd.gz gmail.com> writes:

On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:
 The problem is when I call the save method of the forward range 
 interface I don't get a copy I only get another view to the 
 same state. So when i remove nodes from the original list the 
 range becomes invalid.

This is why modifying a sequence while iterating over it is 
generally forbidden; there's no good way to make it work. You 
could duplicate the entire list for each range, but that's 
expensive for the usual case of simply reading the list.

Forward ranges don't require that ranges be independent of the 
data they iterate over [1]:

 Saving a range is not duplicating it; in the example above, r1
 and r2 still refer to the same underlying data. They just
 navigate that data independently.

IMO your implementation is fine.

[1]: 
http://dlang.org/phobos/std_range_primitives.html#isForwardRange

"anonymous" <anonymous example.com> writes:

On Monday, 6 July 2015 at 20:50:19 UTC, Gary Willoughby wrote:
 How do you correctly implement a bidirectional range on a 
 linked list?

 I have a linked list implementation and I've added a range 
 interface to it but after a while I've realized it not quite 
 right. The problem is when I call the save method of the 
 forward range interface I don't get a copy I only get another 
 view to the same state. So when i remove nodes from the 
 original list the range becomes invalid.

 How can you implement such a range over a type whose state is 
 accessed via pointers?

 Here's my implementation:

 https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L533

There's no requirement for a range to stay valid when the 
underlying container changes. std.container defines "stable" 
variants of the various insertion and removal operations. They 
promise not to invalidate any ranges. When the unstable variants 
are used, it's to be expected that ranges are invalidated.

To make your removal methods stable, it may be enough to not free 
the removed node. That is, don't do this:
https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection

There's a doubly linked list in phobos: std.container.dlist; 
maybe look how things are done there:
https://github.com/D-Programming-Language/phobos/blob/master/std/container/dlist.d

Off topic: I think ` trusted:` is horrible. It's easy to forget 
that you're in a  trusted environment when editing things later. 
And even worse, you're trusting everything that's passed through 
template parameters.

"anonymous" <anonymous example.com> writes:

On Monday, 6 July 2015 at 21:58:31 UTC, anonymous wrote:
 To make your removal methods stable, it may be enough to not 
 free the removed node. That is, don't do this:
 https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection

Looks like I messed up the URL. Here's the right one:

https://github.com/nomad-software/etcetera/blob/master/source/etcetera/collection/linkedlist.d#L205-L206

Jonathan M Davis via Digitalmars-d-learn writes:

On Monday, July 06, 2015 21:58:30 anonymous via Digitalmars-d-learn wrote:
 Off topic: I think ` trusted:` is horrible. It's easy to forget
 that you're in a  trusted environment when editing things later.
 And even worse, you're trusting everything that's passed through
 template parameters.

This is why you almost never use  trusted on templated functions. You should
_never_ mark anything with  trusted unless you can guarantee that it's
actually  safe.  safe is inferred for templated functions, so unless you're
doing  system operations in a templated function, there is no need for
 trusted, and if you are doing  system operations, then they need to be
segregated in a way that you can mark that section of code as  trusted
and guarantee that it's  safe regardless of what the template argument is.
But you should _never_ mark code as  trusted if it involves calling
functions that you can't guarantee are  safe, which almost always means that
you should not mark code which calls functions on template arguments as
 trusted.

That being said,  trusted is very much a necessity in certain types of code,
so it would be really bad if we didn't have it. But if you're marking much
code as  trusted, or if you're marking templated code as  trusted, then you
really need to be examining what you're doing. Very little code should need
to be marked as  trusted, and every time that it is, you need to be able to
absolutely guarantee that it's actually  safe in spite of the  system
operations that you're doing in that code.

- Jonathan M Davis

"Gary Willoughby" <dev nomad.so> writes:

On Tuesday, 7 July 2015 at 09:35:12 UTC, Jonathan M Davis wrote:
 This is why you almost never use  trusted on templated 
 functions. You should
 _never_ mark anything with  trusted unless you can guarantee 
 that it's
 actually  safe.  safe is inferred for templated functions, so 
 unless you're
 doing  system operations in a templated function, there is no 
 need for
  trusted, and if you are doing  system operations, then they 
 need to be
 segregated in a way that you can mark that section of code as 
  trusted
 and guarantee that it's  safe regardless of what the template 
 argument is.
 But you should _never_ mark code as  trusted if it involves 
 calling
 functions that you can't guarantee are  safe, which almost 
 always means that
 you should not mark code which calls functions on template 
 arguments as
  trusted.

 That being said,  trusted is very much a necessity in certain 
 types of code, so it would be really bad if we didn't have it. 
 But if you're marking much code as  trusted, or if you're 
 marking templated code as  trusted, then you really need to be 
 examining what you're doing. Very little code should need to be 
 marked as  trusted, and every time that it is, you need to be 
 able to absolutely guarantee that it's actually  safe in spite 
 of the  system operations that you're doing in that code.

 - Jonathan M Davis

Thanks for the advice.