in std.container, the stable* container functions advocate that they do not invalidate the ranges of their containers. What does it mean to invalidate a range?

my assumption is it means causing e.g. front or popFront to fail when empty says they should succeed or vice versa.

Ellery Newcomer:

> in std.container, the stable* container functions advocate that they do not invalidate the ranges of their containers. What does it mean to invalidate a range?

Generally modifying a collection while you iterate on it causes troubles. When you iterate on a range and you modify the range during the iteration Python gives you an error, because the "for" temporary sets boolean inside the iteratee. In D this problem was avoided in another way, using those stable functions.

Bye,
bearophile

On 08/12/2011 03:13 PM, bearophile wrote:
> Ellery Newcomer:
>
>> in std.container, the stable* container functions advocate that they do
>> not invalidate the ranges of their containers. What does it mean to
>> invalidate a range?
>
> Generally modifying a collection while you iterate on it causes troubles. When you iterate on a range and you modify the range during the iteration Python gives you an error, because the "for" temporary sets boolean inside the iteratee. In D this problem was avoided in another way, using those stable functions.
>
> Bye,
> bearophile

I am not convinced of this. In the following code, there is definitely a problem; it just remains to be seen whether the range is invalidated, or merely noisy according to the specified semantics.


import std.container;
import std.stdio;
import std.array;

void main(){
    auto arr = make!(Array!int)([1,2,3]);
    auto r = arr[];
    writeln(array(r.save()));
    arr.stableRemoveAny();
    writeln(array(r.save()));
}

On Fri, 12 Aug 2011 15:54:53 -0400, Ellery Newcomer <ellery-newcomer@utulsa.edu> wrote:

> in std.container, the stable* container functions advocate that they do not invalidate the ranges of their containers. What does it mean to invalidate a range?

Say for example, you are iterating a red black tree, and your current "front" points at a certain node.  Then that node is removed from the tree.  That range is now invalid, because the node it points to is not valid.

What happens when you use an invalidated range?  Well, we could implement something that throws an exception, but that's an efficiency problem.  I contemplated doing this for debug mode in dcollections, I probably still will.

Another example of an invalidated range, let's say you have a hash map.  The range has a start and a finish, with the finish being iterated after the start.  If you add a node, it could cause a rehash, which could potentially put the finish *before* the start!

However, the same hash implementation could potentially define a stable add, which is guaranteed not to rehash the map, even when it exceeds the rehash threshold :)

-Steve

On 08/12/2011 03:29 PM, Steven Schveighoffer wrote:
> On Fri, 12 Aug 2011 15:54:53 -0400, Ellery Newcomer
> <ellery-newcomer@utulsa.edu> wrote:
>
>> in std.container, the stable* container functions advocate that they
>> do not invalidate the ranges of their containers. What does it mean to
>> invalidate a range?
>
> Say for example, you are iterating a red black tree, and your current
> "front" points at a certain node. Then that node is removed from the
> tree. That range is now invalid, because the node it points to is not
> valid.

Then there is no way to implement a stable remove from a node based container?

> Another example of an invalidated range, let's say you have a hash map.
> The range has a start and a finish, with the finish being iterated after
> the start. If you add a node, it could cause a rehash, which could
> potentially put the finish *before* the start!

Then the invalidation is that the range failed to produce an element of the container?

On Friday, August 12, 2011 12:54 Ellery Newcomer wrote:
> in std.container, the stable* container functions advocate that they do not invalidate the ranges of their containers. What does it mean to invalidate a range?
> 
> my assumption is it means causing e.g. front or popFront to fail when empty says they should succeed or vice versa.

Short answer: The range doesn't point to what it's supposed to point to anymore. Don't use it. Its behavior is undefined.

Long answer: This is a classic issue in C++ with the STL, and it applies to D's ranges for the same reason. An iterator or a range is valid only so long as it continues to point to a valid element in the container that it points to. With a vector or Array for instance, if you have an iterator or range pointer to that vector/Array and the container is reallocated because you appended to it, and it didn't have any capacity left, then you have an iterator/range which points to memory which isn't in the container anymore. Iterating with that iterator/range would be problematic. In C++, you'd likely be iterating over memory which had been deleted, which could cause all kinds of problems and would blow up on you in a variety of ways at least some of the time. In D, the memory is probably still sitting on the stack exactly as it was, so iterating over it would mean iterating over an old version of the container. It probably wouldn't blow up, but it definitely wouldn't be what you wanted. Adding and removing elements without reallocations causes problems too, because the elements get shifted around. The iterator/range may still technically be valid and useable, but it doesn't necessarily point to the same data anymore.

In the case of container that uses nodes - such as a linked list - because you can add and remove elements without affecting other elements, iterators and ranges don't tend to get invalidated as easily. As long as you don't remove the element (or elements in the case of a range - assuming that it keeps track of its two end points, as is likely) that it points to, then adding or removing elements from the container shouldn't invalidate the iterator/range.

So, whether a particular operation invalidates an iterator or range depends very much on the container and the operation. std.container provides stableX functions which do whatever is necessary to guarantee that any ranges which point to the container stay valid. However, any other operation which alters a container risks invalidating any existing range for that container. It may or may not invalidate the range, depending on the container and the operation, but it's a risk. The only way to avoid any risk of invalidating ranges is to not keep ranges over a container when you alter that container.

So, basically what it comes down to is the short answer. A range which has been invalidated doesn't point to what it's supposed to point to anymore, and using it results in undefined behavior. It's less likely to blow up in D, because it's generally memory-safe, but you're going to get incorrect behavior.

- Jonathan M Davis

On Friday, August 12, 2011 13:58 Ellery Newcomer wrote:
> On 08/12/2011 03:29 PM, Steven Schveighoffer wrote:
> > On Fri, 12 Aug 2011 15:54:53 -0400, Ellery Newcomer
> > 
> > <ellery-newcomer@utulsa.edu> wrote:
> >> in std.container, the stable* container functions advocate that they do not invalidate the ranges of their containers. What does it mean to invalidate a range?
> > 
> > Say for example, you are iterating a red black tree, and your current "front" points at a certain node. Then that node is removed from the tree. That range is now invalid, because the node it points to is not valid.
> 
> Then there is no way to implement a stable remove from a node based container?

Removing elements from a node-based container only invalidates ranges if they specifically point to an element which was removed. Whether an iterator is invalidated is more obvious, because it points to a specific element, and as long as it's not the one which was removed, you're fine. For a range, it's not as obvious, because you don't really know how it was implemented internally. However, as long as it's effectively holding the begin and end iterators for the range (which is almost certainly what it has to do), then you know that your rang is fine as long as the first element pointed to and the last elemented pointed to weren't removed. You _do_ have the possible concern that your range doesn't contain the same elements that it did before (if an element was removed from its middle), but the range is still valid.

- Jonathan M Davis

On 08/12/2011 03:54 PM, Jonathan M Davis wrote:
>
> In the case of container that uses nodes - such as a linked list - because you
> can add and remove elements without affecting other elements, iterators and
> ranges don't tend to get invalidated as easily. As long as you don't remove
> the element (or elements in the case of a range - assuming that it keeps track
> of its two end points, as is likely) that it points to, then adding or
> removing elements from the container shouldn't invalidate the iterator/range.

"shouldn't" isn't a guarantee. Where there is "shouldn't", there can't be stableRemove*, no?

>
> So, basically what it comes down to is the short answer. A range which has
> been invalidated doesn't point to what it's supposed to point to anymore, and
> using it results in undefined behavior. It's less likely to blow up in D,
> because it's generally memory-safe, but you're going to get incorrect
> behavior.
>
> - Jonathan M Davis

suppose your linked list range points to a node X. element in X is removed by the linked list, and the range automagically moves to X.next (or X.prev). Is the range invalid by this standard or not? (no way 'san ifrinn I'm going to implement that, though).


heh heh. most of this business has only convinced me I want immutable containers.

On Friday, August 12, 2011 15:29 Ellery Newcomer wrote:
> On 08/12/2011 03:54 PM, Jonathan M Davis wrote:
> > In the case of container that uses nodes - such as a linked list - because you can add and remove elements without affecting other elements, iterators and ranges don't tend to get invalidated as easily. As long as you don't remove the element (or elements in the case of a range - assuming that it keeps track of its two end points, as is likely) that it points to, then adding or removing elements from the container shouldn't invalidate the iterator/range.
> 
> "shouldn't" isn't a guarantee. Where there is "shouldn't", there can't be stableRemove*, no?

An implementation can guarantee it as long as your range doesn't directly point to an element being removed (i.e. as long as the element isn't on the ends - or maybe one past the end, depending on the implementation). But _no_ container can guarantee that an iterator or range which directly references an element which is removed is going to stay valid - not without playing some serious games internally which make iterators and ranges too inefficent, and possibly not even then. So, stableRemove is only going to guarantee that a range stays valid on as long as the end points of that range aren't what was being removed.

> > So, basically what it comes down to is the short answer. A range which has been invalidated doesn't point to what it's supposed to point to anymore, and using it results in undefined behavior. It's less likely to blow up in D, because it's generally memory-safe, but you're going to get incorrect behavior.
> > 
> > - Jonathan M Davis
> 
> suppose your linked list range points to a node X. element in X is removed by the linked list, and the range automagically moves to X.next (or X.prev). Is the range invalid by this standard or not? (no way 'san ifrinn I'm going to implement that, though).

If the element that you removed was the end point of a range, then the range won't be valid anymore.

> heh heh. most of this business has only convinced me I want immutable containers.

It's only an issue if you keep ranges of a container around and then alter the container. If you're just use ranges to do an operation or two and then throw them away, it's not an issue. C++ has been this way for years, and it's generally not a problem. It _can_ be a problem if you try and keep iterators/ranges around while altering a container, but there's not really a good way around that. And as long as you're aware of that, you'll be fine. It's only when you try and alter a container while retaining ranges to it that you're going to have to start worrying about whether a range has been invalidated or not.

- Jonathan M Davis

On 08/12/2011 05:51 PM, Jonathan M Davis wrote:
>
> An implementation can guarantee it as long as your range doesn't directly
> point to an element being removed (i.e. as long as the element isn't on the
> ends - or maybe one past the end, depending on the implementation). But _no_
> container can guarantee that an iterator or range which directly references an
> element which is removed is going to stay valid - not without playing some
> serious games internally which make iterators and ranges too inefficent, and
> possibly not even then. So, stableRemove is only going to guarantee that a
> range stays valid on as long as the end points of that range aren't what was
> being removed.

Forgive my being dense, but where is this 'as long as' coming from? If your range only points to ends in e.g. a linked list, how is it supposed to retrieve elements in the middle? I'm having a hard time visualizing a range over a node based container that doesn't point to a node in the middle (at some point in time). The range points to the node to retrieve the current front quickly, the node can get removed, the removed function won't know its invalidating the range without playing yon internal games, ergo stable remove cannot be.