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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-04-23 07:06:48

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? 

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

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

>>>> 2) allow returning proxy from operator++(int)
>>> 
>>> That doesn't allow all readable single-pass iterators to be input
>>> iterators.  I'm against it.
>>
>> It's possible to require that return value from operator++(int) is
>> some type with operator* and applicatqion of operator* returns the
>> same value as the *it before incrementing.
> 
> Ah, whoops.  OK, that solution is compatible with input iterator and
> output iterator, so I favor it.

Great.

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

> 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 the
   previous value of iterator.

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. So, for forward iterator the above
clause is not necessary. 

> 
>>> I think we need want 1&3.
> 
> Now 2&3.
> 
>> Will 3) require extra storage in iterator?
> 
> Not if accompanied by 2.

That's right.

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

>>> > 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. Does it mean I can go and enable proxy in directory_iterator?
Or, maybe, it's better be addressed in the iterator_facade? 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.

- Volodya