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

From: David Abrahams (dave_at_[hidden])
Date: 2004-04-21 09:57:52

Vladimir Prus <ghost_at_[hidden]> writes:

> David Abrahams wrote:
>
>> The question is, what are the semantics?
>> 
>> Input iterator requirements say:
>> 
>>     Expression    Type    Semantics
>>     ----------    ----    ------------------------------
>>     (void)r++             equivalent to (void)++r
>>     *r++          T       { T tmp = *r; ++r; return tmp; }
>> 
>> But we don't have anything similar in the new concepts.  I guess
>> that's because we're trying to orthogonalize access and traversal, but
>> that may not be possible in this case.  If we don't define the
>> semantics of *r++, a single-pass iterator is free to implement the
>> semantics of *r++ as equivalent to *++r, which is what
>> directory_iterator is doing.
>
> Let me see. The r++ is required to be:
>
>    {
>        X tmp = r;
>        ++r;
>        return tmp;
>    }
>
> After assignment to 'tmp', *tmp returns the right value. After ++r it
> returns different value. 

Right.  That is intentionally allowed for input iterators, and in fact
some do work that way.

> Well, while it seems intuitive that 'tmp' is always equal to itself
> and so *tmp should be always equivivalent to *tmp

I don't understand what any of that means.  Maybe I'm just confused
because it's just too obvious a tautology.

> I agree that this is very loose interpretation of
>
>      pre: a is dereferenceable. If a == b then *a
>      is equivalent to *b.

And I don't see how the above relates to this, either.

> But really, isn't it right to assume that repeating applications of
> operator* with no ++ in between will return the same value? 

I believe that's guaranteed by the above precondition you cited.

>> I'm sure directory_iterator is reporting that its category is
>> input_iterator_tag, so I guess we have a problem in the new
>> iterator concepts and in the iterator_facade implementation here.
>> 
>>> And BTW, don't the above requirements
>> 
>> Which ones?
>
> The requirent that return type of r++ should be X (in Incrementable
> iterator).
>
>>> mean r++ cannot return a proxy object, but only a real copy of the
>>> iterator?

That's right.

>> The input iterator requirements seem to imply that, for true
>> single-pass sequences like streams, either:
>> 
>> a.  the iterator can store a copy of its value_type so that the
>>     iterator returned from r++ can still return the 'tmp' value
>>     indicated above when dereferenced
>> 
>> b.  the iterator can track whether an iterator returned from a
>>     post-increment is "active and not yet dereferenced"
>> 
>> case b. is interesting; it would mean that operator++(int) can set a
>> flag telling the iterator to consume another value before
>> dereferencing.
>
> Oh, it can be described as "deferred post-increment", which is actually done
> only on next deference. But still, won't it reasonable to expect that after
> the following code:
>
>    some_iterator i = ..
>  
>    some_iterator p1 = *i;
                        ^-----you don't mean that, do you?
>    ++i;
>    some_iterator p2 = *i;
>    ++i;
>    ...
>    some_iterator pN = *i;
>
> all iterators are still return the "right" values?

I don't think the standard gives you any assurance of that, and in
fact I doubt that it was intended that input iterators be forced to
store a value, and in fact note 3 in 24.1.1 seems to confirm my doubt:

    -3- [Note: For input iterators, a == b does not imply ++a ==
     ++b. (Equality does not guarantee the substitution property or
     referential transparency.) Algorithms on input iterators should
     never attempt to pass through the same iterator twice. They
     should be single pass algorithms...]

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