[filesystem + iterator] directory iterator problem
There's a bug report on sourceforge: https://sourceforge.net/tracker/index.php?func=detail&aid=937606&group_id=7586&atid=107586 which boils down to the fact that directory_iterator it(...); path p = *it++; does not work correctly. The exact problem is that the above line return a copy of the iterator, and increments 'it', but both iterators have shared_ptr to the same internal structure, so by time user deferences the copy, it gets the next file in the directory. The filesystem lib sources contain the following comment: The *r++ requirement doesn't appear to apply to the new single_pass_traversal category Thus I'm leaving the proxy out pending confirmation from the N1477 authors I'm not sure I understand that. It seems that *r++ should work, since signle pass iterator requires that r++ should work and return object of type X (call it r2), and the reabable iterator requires that *r2 should work. Am I wrong? And BTW, don't the above requirements mean r++ cannot return a proxy object, but only a real copy of the iterator? - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
There's a bug report on sourceforge:
https://sourceforge.net/tracker/index.php?func=detail&aid=937606&group_id=7586&atid=107586
which boils down to the fact that
directory_iterator it(...);
path p = *it++;
does not work correctly. The exact problem is that the above line return a copy of the iterator, and increments 'it', but both iterators have shared_ptr to the same internal structure, so by time user deferences the copy, it gets the next file in the directory.
The filesystem lib sources contain the following comment:
The *r++ requirement doesn't appear to apply to the new single_pass_traversal category Thus I'm leaving the proxy out pending confirmation from the N1477 authors
I'm kinda surprised that nobody asked us about that problem; we can't confirm something we don't know about!
I'm not sure I understand that. It seems that *r++ should work, since signle pass iterator requires that r++ should work and return object of type X (call it r2), and the reabable iterator requires that *r2 should work. Am I wrong?
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. 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?
mean r++ cannot return a proxy object, but only a real copy of the iterator?
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. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
The filesystem lib sources contain the following comment:
The *r++ requirement doesn't appear to apply to the new single_pass_traversal category Thus I'm leaving the proxy out pending confirmation from the N1477 authors
I'm kinda surprised that nobody asked us about that problem; we can't confirm something we don't know about!
It was not me who hasn't asked ;-)
I'm not sure I understand that. It seems that *r++ should work, since signle pass iterator requires that r++ should work and return object of type X (call it r2), and the reabable iterator requires that *r2 should work. Am I wrong?
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. Well, while it seems intuitive that 'tmp' is always equal to itself and so *tmp should be always equivivalent to *tmp, I agree that this is very loose interpretation of pre: a is dereferenceable. If a == b then *a is equivalent to *b. But really, isn't it right to assume that repeating applications of operator* with no ++ in between will return the same value?
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?
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; ++i; some_iterator p2 = *i; ++i; ... some_iterator pN = *i; all iterators are still return the "right" values? - Volodya
Vladimir Prus <ghost@cs.msu.su> 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
David Abrahams wrote:
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.
Could you give some examples?
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 not sure. It's not stated that after X tmp = r; it's true that "tmp == r". Nor I can find statement that "*tmp is the same as *r" after assignment. And if it's guaranteed, then "*tmp" should always return the same value, because tmp itself it not incremented.
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?
Yes, I didn't meant '*'.
++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...]
I read it to mean something different: you can't copy single_pass iterator, increment the original iterator and then take the copy and iterate again. Let me ask a different question: istream_iterator extracts next item in operator++ and stores it inside. It it allowed to implement extraction in operator*(), so that you don't need to store anything at all? I'd say it would be very confusing behaviour. So, istream_iterator really has to store value. And it seems to me, all single pass iterators have to store the value to allow for repeated operator*() calls. The only case when it's not needed is when iterator is a "view" of some other sequence (e.g. filter_iterator). But then iterator keeps a reference to that other sequence, and I don't see why copies of iterator can't retain the same value even if origial iterator is incremented. - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
And it seems to me, all single pass iterators have to store the value to allow for repeated operator*() calls.
Let's talk about concepts in the standard, i.e. input iterator. We invented single pass iterator; it can mean anything we say, and what we said doesn't imply that.
The only case when it's not needed is when iterator is a "view" of some other sequence (e.g. filter_iterator). But then iterator keeps a reference to that other sequence, and I don't see why copies of iterator can't retain the same value even if origial iterator is incremented.
It's not a question of whether they *can* but whether *they're required to*. AFAICT, they are not. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
And it seems to me, all single pass iterators have to store the value to allow for repeated operator*() calls.
Let's talk about concepts in the standard, i.e. input iterator.
Talking about input iterator, directory_iterator does not comply with *r++ requirement.
We invented single pass iterator; it can mean anything we say, and what we said doesn't imply that.
But it's the intention that new-style readable single-pass iterator is also a model of old-style input iterator? And the problem we're discussing is that directory_iterator is readable single-pass iterator but not input iterator? I see that std::input_iterator requirements say that after ++r any copies of the previous value of r are no longer required to be dereferencable. New iterators requirents are silent on this. Is this intentional? If single pass iterator requirements - would add the same note about ++r making iterators dereferencable - retain the same requirements for operator++(int) The result of r++ is not required even to be dereferencable, and *r++ is not required even to be to work for single-pass iterator, while it works for input iterators. The solutions I see are: 1) require that ++r does not makes any copies dereferencable, or 2) allow returning proxy from operator++(int) 3) require that result of r++ is dereferencable and is equivivalent to the dereferencing of the previous value of 'r'. The variant 2) would be most convenient for directory_iterator... - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
And it seems to me, all single pass iterators have to store the value to allow for repeated operator*() calls.
Let's talk about concepts in the standard, i.e. input iterator.
Talking about input iterator, directory_iterator does not comply with *r++ requirement.
Yes, I know.
We invented single pass iterator; it can mean anything we say, and what we said doesn't imply that.
But it's the intention that new-style readable single-pass iterator is also a model of old-style input iterator?
Yes.
And the problem we're discussing is that directory_iterator is readable single-pass iterator but not input iterator?
Yes.
I see that std::input_iterator requirements say that after ++r any copies of the previous value of r are no longer required to be dereferencable.
Right. That rules out your scenario of keeping old copies of the iterator around and derferencing them later.
New iterators requirents are silent on this. Is this intentional?
Probably not. However, if the standard doesn't explicitly guarantee iterator stability, you can't count on it. That said, a note would probably be good to add.
If single pass iterator requirements ^^... - would add the same note about ++r making iterators dereferencable "non-"----------^ Probably a good idea.
- retain the same requirements for operator++(int)
Really you mean requirements on the expression "*r++", I think. ...then what?
The result of r++ is not required even to be dereferencable
Not required by which concept?
and *r++ is not required even to be to work for single-pass iterator, while it works for input iterators.
Right, that needs to be fixed.
The solutions I see are:
1) require that ++r does not makes any copies dereferencable, or
I think you mean "not require that any copies are dereferencable after "++r"?
2) allow returning proxy from operator++(int)
That doesn't allow all readable single-pass iterators to be input iterators. I'm against it. What would the proxy do, anyway?
3) require that result of r++ is dereferencable and is equivivalent to the dereferencing of the previous value of 'r'.
I think we need want 1&3.
The variant 2) would be most convenient for directory_iterator...
Yeah, but it would break interoperability with old algorithms. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
I see that std::input_iterator requirements say that after ++r any copies of the previous value of r are no longer required to be dereferencable.
Right. That rules out your scenario of keeping old copies of the iterator around and derferencing them later.
True. I did not see that clause until yesterday.
New iterators requirents are silent on this. Is this intentional?
Probably not. However, if the standard doesn't explicitly guarantee iterator stability, you can't count on it. That said, a note would probably be good to add.
Okay. BTW, what guarantees that ++r does not invalidate any copies for forward/bidirectional/random iterator?
If single pass iterator requirements ^^... - would add the same note about ++r making iterators dereferencable "non-"----------^ Probably a good idea.
- retain the same requirements for operator++(int)
Really you mean requirements on the expression "*r++", I think.
No, on operator++(int)
...then what?
The result of r++ is not required even to be dereferencable
Not required by which concept?
By nothing I could find in new iterator requirements. Requirements on operator++(int) say: { X tmp = r; ++r; return tmp; } operator++ is allowed to invalidate 'tmp', and nothing explicitly requires return value from operator++(int) to be dereferencable.
The solutions I see are:
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 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.
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 application of operator* returns the same value as the *it before incrementing.
What would the proxy do, anyway?
Here's commented out code in filesystem lib: struct path_proxy // allows *r++ to work, as required by 24.1.1 { path pv; explicit path_proxy( const path & p ) : pv(p) {} path operator*() const { return pv; } }; path_proxy operator++(int) { path_proxy pp( m_deref() ); ++*this; return pp; }
3) require that result of r++ is dereferencable and is equivivalent to the dereferencing of the previous value of 'r'.
I think we need want 1&3.
Will 3) require extra storage in iterator? 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). Besides, In the second case it should be stated that return of r++ is dereferencable untill you call operator*() or operator++() on original iterator.
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++. - Volodya Yeah, but it would break interoperability with old algorithms.
Vladimir Prus <ghost@cs.msu.su> writes:
Okay. BTW, what guarantees that ++r does not invalidate any copies for forward/bidirectional/random iterator?
None, I think.
If single pass iterator requirements ^^... - would add the same note about ++r making iterators dereferencable "non-"----------^ Probably a good idea.
- retain the same requirements for operator++(int)
Really you mean requirements on the expression "*r++", I think.
No, on operator++(int)
What requirements do you mean, specifically?
...then what?
No answer? You started a phrase with if (condition) but there was no "body", if you will.
The result of r++ is not required even to be dereferencable
Not required by which concept?
By nothing I could find in new iterator requirements. Requirements on operator++(int) say:
{ X tmp = r; ++r; return tmp; }
Right. Traversal and access are supposed to be orthogonal.
operator++ is allowed to invalidate 'tmp', and nothing explicitly requires return value from operator++(int) to be dereferencable.
Right. That's why we need to somehow retain the requirements for *r++.
The solutions I see are:
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."
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.
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.
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++". The question is, in which concept does that requirement go? It's neither a pure access nor a pure traversal concept.
I think we need want 1&3.
Now 2&3.
Will 3) require extra storage in iterator?
Not if accompanied by 2.
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
Besides, In the second case it should be stated that return of r++ is dereferencable untill you call operator*() or operator++() on original iterator.
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. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
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
Vladimir Prus <ghost@cs.msu.su> 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...
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
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... 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
Vladimir Prus <ghost@cs.msu.su> writes:
where rv is the return value ^^^^^^^^^^^^ of what?
Of the "*rv" expression.
I'm confused. You're saying *rv is equivalent to rv ?? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
where rv is the return value ^^^^^^^^^^^^ of what?
Of the "*rv" expression.
I'm confused. You're saying *rv is equivalent to rv ??
Ok, let me try again: if iterator is also a model of the readable iterator concept, then    expression *rv should be equal to *v, where v is the value of iterator before call to operator++(int) and rv is the value returned from the call. The good question is what 'equal' means? Operator== might not be defined. The standard uses 'equivalent' but I don't know what that means. - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
where rv is the return value ^^^^^^^^^^^^ of what?
Of the "*rv" expression.
I'm confused. You're saying *rv is equivalent to rv ??
Ok, let me try again:
if iterator is also a model of the readable iterator concept, then    expression *rv should be equal to *v, where v is the value of iterator before call to operator++(int) and rv is the value returned from the call.
We don't need new language to express what should be said here; we can just take it from the C++98 input iterator requirements. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Ok, let me try again:
if iterator is also a model of the readable iterator concept, then expression *rv should be equal to *v, where v is the value of iterator before call to operator++(int) and rv is the value returned from the call.
We don't need new language to express what should be said here; we can just take it from the C++98 input iterator requirements.
Except that requirements on "*r" return return say: "Convertible to T" and std::input_iterator requirements on "*r++" say the return type should be "T", exactly. I'm not sure what problems this entail, just pointing out the difference. - Volodya
Vladimir Prus <ghost@cs.msu.su> 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...
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
David Abrahams wrote:
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,
What's 'referent stability'?
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.
Yes, that's okay. The property I was asking about is that in the following code: X it = ... X c = it; *it; ++it; *c; the values returned by both operator*() calls are the same. I always had assumption that for std::forward_iterator this is true. Unfortunately, after 20 mins of looking at the requirements I can't prove that, gotta take a second look.
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.
How? I can't decude that from any of singla pass iterator requirements.
If so, then both old and new requirements are equivivalent w.r.t. invalidation of copies.
I don't understand.
Ok, nevermind.
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.
Great.
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
Ok.
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?
"it" = iterator_facede. can be used = can be used for making writable iterators (which are not lvalue iterators).
but it that I'm not sure what operator++(int) should return...
That's the important question. Writable non-lvalue iterator cannot return a proxy storing the value inside, since there's no value to store. So making iterator_facade return proxy with stored value for all non-lvalue iterators is too simple solution :-(
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.
At least, there are requirements, which makes it possible to say "your iterator violates standard requirements", which is much better that "your iterator is strange" ;-) - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
David Abrahams wrote:
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,
What's 'referent stability'?
the stability of "what's referred to" by the iterator.
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.
Yes, that's okay. The property I was asking about is that in the following code:
X it = ... X c = it; *it; ++it; *c;
the values returned by both operator*() calls are the same.
I always had assumption that for std::forward_iterator this is true. Unfortunately, after 20 mins of looking at the requirements I can't prove that, gotta take a second look.
OK.
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.
How? I can't decude that from any of singla pass iterator requirements.
Incrementable iterator is a refinement of Assignable and Copy Constructible, and == is an equivalence relation, etc.
but it that I'm not sure what operator++(int) should return...
That's the important question. Writable non-lvalue iterator cannot return a proxy storing the value inside, since there's no value to store. So making iterator_facade return proxy with stored value for all non-lvalue iterators is too simple solution :-(
Ugh, right. I'll try to discuss this stuff with Jeremy when I see him tomorrow.
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.
At least, there are requirements, which makes it possible to say "your iterator violates standard requirements", which is much better that "your iterator is strange" ;-)
Definitely. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
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,
What's 'referent stability'?
the stability of "what's referred to" by the iterator.
E.g. stability of *reference*? Or stability of the referred value?
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.
How? I can't decude that from any of singla pass iterator requirements.
Incrementable iterator is a refinement of Assignable and Copy Constructible, and == is an equivalence relation, etc.
equivalence relation, in mathematical sense is a relation which is reflexive, transitive, and symmentric. Hmm.. I guess I only need to understand this requirement for Assignable: t = u post: t is equivalent to u ... - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
but it that I'm not sure what operator++(int) should return...
That's the important question. Writable non-lvalue iterator cannot return a proxy storing the value inside, since there's no value to store. So making iterator_facade return proxy with stored value for all non-lvalue iterators is too simple solution :-(
Actually I think a proxy storing the iterator_facade's "reference" type is probably enough. Think about it. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
but it that I'm not sure what operator++(int) should return...
That's the important question. Writable non-lvalue iterator cannot return a proxy storing the value inside, since there's no value to store. So making iterator_facade return proxy with stored value for all non-lvalue iterators is too simple solution :-(
Actually I think a proxy storing the iterator_facade's "reference" type is probably enough. Think about it.
For writable iterators, that's fine (well, provided it's required that return type of *a is iterator_traits<X>::reference). For readable iterators, you have to store value_type, not reference, since if you store reference, *r++ won't work. The question is how to distinguish between readable and writable iterators. Maybe, using 'is_convertible' on the reference type? BTW, are there any examples of writable iterator made with iterator facade? - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
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.
Great.
Looks like you never did this? I'm going to try to fix iterator_facade to handle these cases. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
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.
Great.
Looks like you never did this?
No. I've sent a patch to Beman, but he did not comment. Do you have an idea if he's available?
I'm going to try to fix iterator_facade to handle these cases.
Great. - Volodya
Vladimir Prus <ghost@cs.msu.su> writes:
David Abrahams wrote:
Vladimir Prus <ghost@cs.msu.su> writes:
> 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.
Great.
Looks like you never did this?
No. I've sent a patch to Beman, but he did not comment. Do you have an idea if he's available?
He's not; he's recovering (successfully) from an illness. I expect him back in a month or so.
I'm going to try to fix iterator_facade to handle these cases.
Great.
We have a bit of a problem since an input iterator can never be an output iterator due to the requirement that *r++ returns T. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (2)
-
David Abrahams -
Vladimir Prus