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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-23 09:38:28

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.

BTW, do new iterator requirement state that iterator type X is interoperable
with itself? If so, then both old and new requirements are equivivalent
w.r.t. invalidation of copies.

>>>> then *r++ will be guaranteed to work. OTOH, this would require
>>>> storing value in iterator which as you say is not indented by current
>>>> input_iterator.
>>> 
>>> Yes, and it mean that not all readable single-pass iterators are input
>>> iterators, so I'm against it.
>>
>> What input iterators requirements will be violated?
> 
> Sorry, I got it backwards.  Not all input iterators will be readable
> single-pass iterators.  Either way, it creates a problem I think.

Right, I think directory_iterator will be affected, in particular.
 
>>>>>> 3) require that result of r++ is dereferencable and is equivivalent
>>>>>> to the dereferencing of the previous value of 'r'.
>>> 
>>> Well, that requirement is equivalent to input iterator's requirement
>>> on "*r++".
>>
>> In fact (3) is a bit stronger:
>>
>>    iterator copy = it++;
>>    value_type v = *copy;
>>
>> is required to work by it, while standard input iterators are required to
>> support *r++ as a single lexical expression.
> 
> In that case, I don't want to ask for what you intend by 3, because
> it means not all input iterators will be readable single-pass
> iterators.

Ok, agreed.

>>> 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.

>> 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...

>> 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.

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

Okay, I'm going ahead.

>> Or, maybe, it's better be addressed in the iterator_facade?
> 
> Yes, IMO, but I am wondering how it should be done?
> 
>> 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? Or iterator_facace can be used for
making writable iterators? I 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.

- Volodya