[boost] Re: [filesystem + iterator] directory iterator problem

From: David Abrahams (dave_at_[hidden])
Date: 2004-04-23 14:16:25

Vladimir Prus <ghost_at_[hidden]> writes:

> David Abrahams wrote:
>
>>> Hmm... then shouldn't it be guaranteed somehow?
>> 
>> Well, I may have been wrong.  The forward iterator requirements say:
>> 
>>   expression  operational semantics   assertion
>>   ----------  ---------------------   ---------
>>   ++r                                 r == s and r is dereferenceable
>>                                       implies ++r == ++s .
>> 
>> 
>>   X u(a);     X u; u = a;             post: u == a .
>
> Oh, yea. Together with requirement that "r == s" implies "*r == *s" it seems
> to guarantee that ++ does not invalidate copies.

I don't think you need that other requirement.  Remember, an invalid
iterator can't be incremented.  So if r is dereferenceable, it's
valid. You're still allowed to increment s (a copy of r) after r is
incremented, so it can't have been invalidated by incrementing r.

If you're interested in *referent stability* of copies of r, I'm not
sure that anything guarantees it.  In other words, nothing guarantees
that t is valid after:

    T& t = *r++;

Indeed, some forward iterators actually store the value_type object
that they reference.

> BTW, do new iterator requirement state that iterator type X is
> interoperable with itself? 

Not explicitly, but that is certainly a logical implication of the
requirements on single pass iterators.

> If so, then both old and new requirements are equivivalent
> w.r.t. invalidation of copies.

I don't understand.

>>>> The question is, in which concept does that requirement
>>>> go?  It's neither a pure access nor a pure traversal concept.
>>>
>>> And this requirements does not make sense for writable iterators... maybe
>>> it can be documented in single_pass iterator, like:
>>>
>>>    if iterator is also a model of the readable iterator concept, then
>>>    expression *rv, where rv is the return value should be equal to
>>                                      ^^^^^^^^^^^^
>>                                      of what?
>
> Of the "*rv" expression.
>
>>>    the previous value of iterator.
>> 
>> I don't understand it, but I think something along those lines will be
>> needed.  We can probably use the "pre:" construct as shown in
>>
> http://tinyurl.com/2dm3h#random-access-traversal-iterators-lib-random-access-traversal-iterators
>
> Yea, that's possible.

OK.

>>> The requirements for forward_iterator can specify that operator++ does
>>> not invalidate any copies of the iterator and does not change the value
>>> returned from operator*() of copies.
>> 
>> Huh?  I can't change the forward iterator requirements.
>
> Ah, I mean "forward traversal iterator" and anyway this is already
> guaranteed...

OK.

>>> That's great.
>> 
>> Well, but we weren't on the same page about the meaning of 3.
>
> Hopefully we're on the same page now.

I think so.

>>> Does it mean I can go and enable proxy in directory_iterator?
>> 
>> Well sure, I think that was always legal.

I guess I was wrong to say that it was always legal.  But it was
never our intention to outlaw it.

>>> Say, so that proxy is always used for readable single-pass
>>> iterators? I guess if iterator stores a value inside, it can always
>>> to lvalue iterator, so always using proxy for readable iterators
>>> seems OK.
>> 
>> Maybe it'd be best to use a proxy only for non-lvalue iterators?
>
> Isn't non-lvalue the same as readable? 

No:

    1. an lvalue iterator may certainly be readable

    2. a writable iterator that isn't also readable can't possibly be
       an lvalue iterator

> Or iterator_facace can be used for making writable iterators? 

It certainly can... but I don't see what you're getting at.

> I think it can be used

What's "it" and how do you think it can be used?

> but it that I'm not sure what operator++(int) should return...

>> Thanks for your attention to this; it makes a big difference!
>
> You're welcome. In fact, I only now understood how complex iterators are --
> due to this discussion and a couple of other iterator-releated issued I had
> today. It's really good there are formal requirements.

Yeah.  Well, the ones in the standard a sort of a mess, which makes
writing backward-compatible "new requirements" a lot harder than it
would otherwise be.

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com