[iterator_facade] postfix ++/--
I'm getting ready to fix the issues we've discussed with postfix ++ (and by extension, --) in iterator_facade. Basically, the current implementation works for forward iterators but not for some input iterators: { self x = *this; ++*this; // <== here return x; } The problem is that for many input iterators, all copies reference the same element. The marked line increments the iterator, which causes the current element of the sequence to be skipped, so *a++ yields the /next/ element. To fix that, a++ needs to return a proxy type. When considering this stuff, please look at n1640 and not C++98 or TC1, as n1640 contains fixes for outright bugs that survived to TC1 as well. In particular, *a++ was required to return an input iterator's value_type until recently. If we don't know for certain that the iterator is a forward iterator and if *a returns something convertible to T const& (where T is the iterator's value type) it seems to me that we *must* assume that all copies of the iterator reference the same element, so the result of postfix ++ must be a proxy that contains a copy of *a. The new iterator framework is intended to support iterators with bidirectional traversal that are not conforming forward iterators (e.g. their operator* may return by-value). If an iterator is incrementable it is also dereferenceable, but the same doesn't hold for decrementability, so I'm not sure what to do about the result of postfix --. The best solution I can think of is that the actual decrement is delayed, and the iterator being decremented contains a flag that says "do an extra decrement before the next operation other than postfix decrement". That's a really bad solution, though: you can't really do a decrement in the destructor because it might throw, and such an iterator could easily have side-effects, so it'd be easy to get the iterator out-of-synch with expectations. Thoughts? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
I'm getting ready to fix the issues we've discussed with postfix ++ (and by extension, --) in iterator_facade. Basically, the current implementation works for forward iterators but not for some input iterators:
{ self x = *this; ++*this; // <== here return x; }
The problem is that for many input iterators, all copies reference the same element. The marked line increments the iterator, which causes the current element of the sequence to be skipped, so
*a++
yields the /next/ element. To fix that, a++ needs to return a proxy type.
When considering this stuff, please look at n1640 and not C++98 or TC1, as n1640 contains fixes for outright bugs that survived to TC1 as well. In particular, *a++ was required to return an input iterator's value_type until recently.
If we don't know for certain that the iterator is a forward iterator and if *a returns something convertible to T const& (where T is the iterator's value type) it seems to me that we *must* assume that all copies of the iterator reference the same element, so the result of postfix ++ must be a proxy that contains a copy of *a.
The new iterator framework is intended to support iterators with bidirectional traversal that are not conforming forward iterators (e.g. their operator* may return by-value). If an iterator is incrementable it is also dereferenceable, but the same doesn't hold for decrementability, so I'm not sure what to do about the result of postfix --.
The best solution I can think of is that the actual decrement is delayed, and the iterator being decremented contains a flag that says "do an extra decrement before the next operation other than postfix decrement". That's a really bad solution, though: you can't really do a decrement in the destructor because it might throw, and such an iterator could easily have side-effects, so it'd be easy to get the iterator out-of-synch with expectations.
Actually there's no problem. The only iterators that need this sort of help with postfix increment are those that "consume" their inputs -- in other words, those that are not multipass iterators. All of the iterator concepts with bidirectional traversal capability are multipass. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
I'm getting ready to fix the issues we've discussed with postfix ++ (and by extension, --) in iterator_facade. Basically, the current implementation works for forward iterators but not for some input iterators:
{ self x = *this; ++*this; // <== here return x; }
The problem is that for many input iterators, all copies reference the same element. The marked line increments the iterator, which causes the current element of the sequence to be skipped, so
*a++
yields the /next/ element. To fix that, a++ needs to return a proxy type.
Fixed now in CVS, along with new tests. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Unfortunately, with the new iterator_facade implementation, filesystem/src/path_posix_windows.cpp" can not compile on Compaq Tru64 (cxx). cxx: Error: /usr/lib/cmplrs/cxx/V6.5-034/include/cxx/algorithm.cc, line 2582: no operator "<" matches these operands operand types are: const boost::detail::postfix_increment_proxy<boost::filesystem: :path::iterator> < const boost::detail::postfix_increment_proxy<boost::filesystem: :path::iterator> detected during instantiation of "bool std::lexicographical_compare(InputIterator1, InputIterator1, InputIterator2, InputIterator2) [with InputIterator1=boost::filesystem::path::iterator, InputIterator2=boost::filesystem::path::iterator]" if (*first2++ < *first1++) return false; --------------------^ cxx: Info: 1 error detected in the compilation of "XXX/src/boost/libs/filesystem/src/path_posix_windows.cpp". Do you have any idea to fix this problem?? Best regards, Synge From: David Abrahams <dave@boost-consulting.com> Date: Sun, 11 Jul 2004 23:18:07 -0400
David Abrahams <dave@boost-consulting.com> writes:
I'm getting ready to fix the issues we've discussed with postfix ++ (and by extension, --) in iterator_facade. Basically, the current implementation works for forward iterators but not for some input iterators:
{ self x = *this; ++*this; // <== here return x; }
The problem is that for many input iterators, all copies reference the same element. The marked line increments the iterator, which causes the current element of the sequence to be skipped, so
*a++
yields the /next/ element. To fix that, a++ needs to return a proxy type.
Fixed now in CVS, along with new tests. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Synge Todo <wistaria@comp-phys.org> writes:
Unfortunately, with the new iterator_facade implementation, filesystem/src/path_posix_windows.cpp" can not compile on Compaq Tru64 (cxx).
cxx: Error: /usr/lib/cmplrs/cxx/V6.5-034/include/cxx/algorithm.cc, line 2582: no operator "<" matches these operands operand types are: const boost::detail::postfix_increment_proxy<boost::filesystem: :path::iterator> < const boost::detail::postfix_increment_proxy<boost::filesystem: :path::iterator> detected during instantiation of "bool std::lexicographical_compare(InputIterator1, InputIterator1, InputIterator2, InputIterator2) [with InputIterator1=boost::filesystem::path::iterator, InputIterator2=boost::filesystem::path::iterator]" if (*first2++ < *first1++) return false; --------------------^ cxx: Info: 1 error detected in the compilation of "XXX/src/boost/libs/filesystem/src/path_posix_windows.cpp".
Do you have any idea to fix this problem??
Yeah :( It appears that the old input iterator requirements require that *r++ returns value_type instead of a proxy. However, *r++ must be a proxy if the iterator is writable. Since there's no way to detect iterator writability reliably, I'm going to have to make *r++ return value_type whenever the specified iterator category is strictly std::input_iterator_tag. I'll let everyone know when it's checked in. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
On Jul 13, 2004, at 5:49 AM, David Abrahams wrote:
Synge Todo <wistaria@comp-phys.org> writes: It appears that the old input iterator requirements require that *r++ returns value_type instead of a proxy. However, *r++ must be a proxy if the iterator is writable. Since there's no way to detect iterator writability reliably, I'm going to have to make *r++ return value_type whenever the specified iterator category is strictly std::input_iterator_tag.
I'll let everyone know when it's checked in
FYI, the operations_test.cpp test of the filesystem lib fails unless the return type of *r++ is value_type (where r is a directory_iterator). The problematic line is, of course: BOOST_TEST( (*dir_itr++).leaf() == "d2" ); directory_iterator uses single_pass_traversal_tag, not std::input_iterator_tag. Granted, there's a big comment in that same block of code (near line 100 of boost/filesystem/operations.hpp) that indicates how unsure the author was about proxies :) Doug
Doug Gregor <dgregor@cs.indiana.edu> writes:
On Jul 13, 2004, at 5:49 AM, David Abrahams wrote:
Synge Todo <wistaria@comp-phys.org> writes: It appears that the old input iterator requirements require that *r++ returns value_type instead of a proxy. However, *r++ must be a proxy if the iterator is writable. Since there's no way to detect iterator writability reliably, I'm going to have to make *r++ return value_type whenever the specified iterator category is strictly std::input_iterator_tag.
I'll let everyone know when it's checked in
FYI, the operations_test.cpp test of the filesystem lib fails unless the return type of *r++ is value_type (where r is a directory_iterator). The problematic line is, of course:
BOOST_TEST( (*dir_itr++).leaf() == "d2" );
directory_iterator uses single_pass_traversal_tag, not std::input_iterator_tag. Granted, there's a big comment in that same block of code (near line 100 of boost/filesystem/operations.hpp) that indicates how unsure the author was about proxies :)
Yeah, I decided that we'd only make a writable proxy for *r++ if the facade's CategoryOrTraversal parameter is convertible to std::output_iterator_tag. It's the best thing I can think of, since I expect that building output iterators with iterator_facade is rare. Tests seem to be passing now; I'll check things in shortly. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Doug Gregor <dgregor@cs.indiana.edu> writes:
On Jul 13, 2004, at 5:49 AM, David Abrahams wrote:
Synge Todo <wistaria@comp-phys.org> writes: It appears that the old input iterator requirements require that *r++ returns value_type instead of a proxy. However, *r++ must be a proxy if the iterator is writable. Since there's no way to detect iterator writability reliably, I'm going to have to make *r++ return value_type whenever the specified iterator category is strictly std::input_iterator_tag.
I'll let everyone know when it's checked in
FYI, the operations_test.cpp test of the filesystem lib fails unless the return type of *r++ is value_type (where r is a directory_iterator). The problematic line is, of course:
BOOST_TEST( (*dir_itr++).leaf() == "d2" );
Actually, looking at the test, it's just wrong by any measure. The only thing it was compatible with was the old broken semantics for iterator_facade's postfix increment when it was implementing an input iterator. To be consistent with C++98, it should be BOOST_TEST( (*dir_itr++).leaf() == "d1" ); ^ And to be consistent with the current WP, it should be BOOST_TEST(implicit_cast<std::string const&>((*dir_itr++)).leaf() == "d1" ); I'll update the test appropriately. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
Doug Gregor <dgregor@cs.indiana.edu> writes:
On Jul 13, 2004, at 5:49 AM, David Abrahams wrote:
Synge Todo <wistaria@comp-phys.org> writes: It appears that the old input iterator requirements require that *r++ returns value_type instead of a proxy. However, *r++ must be a proxy if the iterator is writable. Since there's no way to detect iterator writability reliably, I'm going to have to make *r++ return value_type whenever the specified iterator category is strictly std::input_iterator_tag.
I'll let everyone know when it's checked in
FYI, the operations_test.cpp test of the filesystem lib fails unless the return type of *r++ is value_type (where r is a directory_iterator). The problematic line is, of course:
BOOST_TEST( (*dir_itr++).leaf() == "d2" );
Actually, looking at the test, it's just wrong by any measure. The only thing it was compatible with was the old broken semantics for iterator_facade's postfix increment when it was implementing an input iterator. To be consistent with C++98, it should be
BOOST_TEST( (*dir_itr++).leaf() == "d1" ); ^
And to be consistent with the current WP, it should be
BOOST_TEST(implicit_cast<std::string const&>((*dir_itr++)).leaf() == "d1" );
I'll update the test appropriately.
OK, all fixed and checked in. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
OK, all fixed and checked in.
One more word about this fix: iterator_facade now has to choose between *r++ = o being valid and being a conforming TR1 input iterator (which requires *r++ is of type T -- we have since declared that a defect and *r++ need only be convertible to T). It makes that choice by looking at the CategoryOrTraversal parameter: iff it's convertible to std::output_iterator_tag, *r++ = o will be valid. I am thinking it might be more appropriate to detect that *r is a proxy, and only make *r++ = o valid in that case. Can anyone think of a reason that a non-writable iterator implementation would need to return a proxy from its operator*? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (3)
-
David Abrahams -
Doug Gregor -
Synge Todo