Safe Cursors and Ranges

[Steven Schveighoffer]

On Thu, 26 Aug 2010 11:17:32 -0400, Pillsy <pillsbury at gmail.com> wrote:

> Steven Schveighoffer Wrote:
>
>> On Thu, 26 Aug 2010 10:18:51 -0400, Pillsy <pillsbury at gmail.com>
>> wrote:
> [...]
>> > The key idea is that these cursors aren't a primitive part of a
>> > range; instead, they take a range and add a position *inside*
>> > the range. They're a perfect fit for all those "three-legged"
>> > operations out there because they actually have three legs.
> [...]
>> The 'three-legged' cursor as you propose was an early idea of
>> mine too.
>
> If you don't mind me asking, what made you give up on it?

A cursor that refers to one element is much more efficient to pass  
around/copy.  Plus the extra baggage was not needed in dcollections -- any  
operations you perform on a cursor besides changing the value require you  
to have the container also (i.e. a cursor is mainly a parameter to the  
container).  I don't know how this relates to three-legged algorithms and  
straight ranges+cursors, dcollections ranges+cursors would need some extra  
binding support to use them, since you need the container to create a  
range based on two cursors.

>
>> My view is that a cursor should be separate from a range, and a
>> range should either be able to tell if a cursor is part of it (@safe)
>> or be told  that a cursor is a part of it (@system or @trusted).
>
> What's the advantage of not holding on to the range as part of the
> cursor? I'm more focused on the typical value-type ranges, but I'm
> not seeing a lot of need for cursors that have lives independent of
> underlying ranges. Is the concern just one of more frequent
> invalidation?

Because some cursors do not need the hard reference, it is trivial to tell  
whether such cursors belong to a range.  For instance, it's trivial to  
tell that a pointer is part of an array.  So a cursor for an array would  
not need to refer the range it belongs to.

For instance, if I have an array, and a cursor in that array, it's trivial  
for an allBefore operation to determine that the cursor is a member of the  
array.  Now, let's say we have two slices that contain the same cursor, in  
your scheme, in order to use one cursor against the other range, you need  
to recompose the cursor, which seems unnecessarily awkward.  Such a scheme  
is not possible on other ranges, but that just means those ranges don't  
support safe calls for allBefore and the like.  For those ranges, a  
3-legged type would be appropriate, but the 3-legged thing could be a  
combination of a cursor and a range, with the cursor proven to be part of  
the range -- an invariant of the 3-legged type.

Having a cursor point to exactly one element allows more flexibility,  
because you could use a cursor with multiple ranges.  It also decouples  
the cursor from a range that might be superfluous information.  For  
example, if I want to store a link list element cursor so I can change it  
later, why do I also have to carry around the baggage of the range it came  
from?

One of the drawbacks is the cursor cannot move to other elements or alter  
topology, it's strictly a reference-only.  Another reason to have the  
3-legged type.

>
> IME, three-legged operations are fairly common, but four- and more-
> legged operations which can't be easily decomposed into consecutive
> three-legged operations are very uncommon.

I have no experience with three-legged operations.  I just looked at  
cursors from the point of view of reference to a single element.  Such an  
ability is important for a container library.

I can see such an ability being important for simple operations as well,  
not just algorithms.

> What I'm thinking is that cursors aren't skinny ranges, they're ranges
> that are even fatter. You simply wouldn't use one where a range
> would suffice. Allowing questions about whether a range contains a
> cursor or not strikes me as just buying trouble.

But you don't always care if a cursor is a part of a range.  For example,  
to change or refer to a specific element of a range, why do you need to  
refer to the range also?  The composition of a range and cursor together  
can be guarded by @system or @trusted indicating the type system is taking  
your word for it, but in some cases, it can be proven without assumption  
(i.e. arrays).

I don't have a problem with defining such a three-legged type, but can we  
call it something besides a cursor?  Not that I have a trademark or  
anything, but it would be really confusing to have it mean two different  
things depending on context :)

As I said, I can see utility in having a three-legged beast that combines  
a cursor and a range, but I see value in having a simple one-element  
cursor as well.

-Steve