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

From: David Abrahams (dave_at_[hidden])
Date: 2004-04-23 08:41:44

Vladimir Prus <ghost_at_[hidden]> writes:

> David Abrahams wrote:
>
>>> Okay. BTW, what guarantees that ++r does not invalidate any copies for
>>> forward/bidirectional/random iterator?
>> 
>> None, I think.
>
> 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 . 

>>>> Really you mean requirements on the expression "*r++", I think.
>>>
>>> No, on operator++(int)
>> 
>> What requirements do you mean, specifically?
>
> The 
>   {
>        X tmp = r;
>        ++r;
>        return tmp;
>   }
> requirement I quote below.
>
>>>>     ...then what?
>> 
>> No answer?  You started a phrase with if (condition) but there was no
>> "body", if you will.
>
> Ah, understand. The "body" was
>
>     The result of r++ is not required even to be dereferencable
>
> It only lacked "then".

Oh, OK.

>>>>> 1) require that ++r does not makes any copies dereferencable, or
>>>> 
>>>> I think you mean "not require that any copies are dereferencable after
>>>> "++r"?
>>>
>>> Nope, I meant what written. If ++r is required to keep the copies
>>> deferencable
>> 
>> That's the opposite of what you wrote. "does not makes any copies
>> dereferencable" means, "doesn't change any copies of r from
>> non-dereferenceable to dereferenceable."
>
> Oops, sorry for confusion, I've got lost in 'de-' and 'non-' prefixes.
>
>>> 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.

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

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

>    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

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

>>> Now, transform_iterator can store only wrapped iterator and a
>>> functor. If 3) is required it should additionally store either
>>> value, or a flag telling there's a undereferenced copy (as you've
>>> suggested).
>> 
>> I don't think the flag will work, actually, because of this
>> requirement on input iterator:
>> 
>>   operation   semantics
>>   ---------   -----------------------
>>   (void)r++   equivalent to (void)++r
>
> Isn't this "equivalent" means "in observable behaviour"? If so, it doesn't
> matter if r++ get new item immediately or sets a flag. By the time you
> derefence iterator, there's new value and user has no way to detect that
> some flag is used.

Ah, right.  The flag is set in the iterator that got postincremented,
not the copy that was returned by the postincrement.

>>>> > The variant 2) would be most convenient for directory_iterator...
>>>
>>>> Yeah, but it would break interoperability with old algorithms.
>>>
>>> Why? Input iterator requirements only say that *r++ should return T. They
>>> don't say anything about type of r++.
>> 
>> You're right.  It's 2&3.
>
> That's great. 

Well, but we weren't on the same page about the meaning of 3.

> Does it mean I can go and enable proxy in directory_iterator?

Well sure, I think that was always legal.

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

Thanks for your attention to this; it makes a big difference!

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