The documented requirement of pop_back are wrong. The docs say that pop_back works on Forward Sequences, however the following does not compile: // ERROR fusion::list<int, int> l(1, 2); fusion::pop_back(l); The problem is that the implementation of pop_back uses prior, which only works on Bidirectional Sequences. That's merely a doc problem, but this is a more serious problem: // ERROR fusion::pop_back(fusion::pop_back( fusion::push_back(fusion::push_back(fusion::nil(), 1), 2))); A sequence created by push_back is a Forward Sequence, which means you can't call pop_back on it. I think that's a serious shortcoming. Fusion needs something like MPL's Back Extensible and Front Extensible concepts. http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/refmanual/back-extensible-... Unfortunately, this would likely require a redesign of the whole (push|pop)_(front|back) mechanism. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/10/2011 12:56 PM, Eric Niebler wrote:
The documented requirement of pop_back are wrong. The docs say that pop_back works on Forward Sequences, however the following does not compile:
// ERROR fusion::list<int, int> l(1, 2); fusion::pop_back(l);
The problem is that the implementation of pop_back uses prior, which only works on Bidirectional Sequences.
That's merely a doc problem, but this is a more serious problem:
// ERROR fusion::pop_back(fusion::pop_back( fusion::push_back(fusion::push_back(fusion::nil(), 1), 2)));
A sequence created by push_back is a Forward Sequence, which means you can't call pop_back on it. I think that's a serious shortcoming. Fusion needs something like MPL's Back Extensible and Front Extensible concepts.
http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/refmanual/back-extensible-...
Unfortunately, this would likely require a redesign of the whole (push|pop)_(front|back) mechanism.
Man, this is a major bummer, alright. One plausible clean way I can think of is: 1) Make single_view random_access (if it's not already; IIRC No). 2) Make joint_view assume the least sequence category of its subsumed sequences. There's already some work done related to this where joint_view inherits the 'associative'-ness of its held sequences. I think this is an implementable clean solution. I'll see if I can work on it. Yours is a good test case. Thanks for noticing this, Eric! Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/9/2011 11:17 PM, Joel de Guzman wrote:
On 8/10/2011 12:56 PM, Eric Niebler wrote:
A sequence created by push_back is a Forward Sequence, which means you can't call pop_back on it. I think that's a serious shortcoming. Fusion needs something like MPL's Back Extensible and Front Extensible concepts.
http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/refmanual/back-extensible-...
Unfortunately, this would likely require a redesign of the whole (push|pop)_(front|back) mechanism.
Man, this is a major bummer, alright. One plausible clean way I can think of is:
1) Make single_view random_access (if it's not already; IIRC No).
I implemented this not too long ago.
2) Make joint_view assume the least sequence category of its subsumed sequences. There's already some work done related to this where joint_view inherits the 'associative'-ness of its held sequences.
I don't think that's good enough. Take my example above. In, push_back(nil(), 1), the traversal type of nil is Forward, and so too would be the resulting view. It probably makes sense to see how MPL manages it. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/10/2011 2:51 PM, Eric Niebler wrote:
On 8/9/2011 11:17 PM, Joel de Guzman wrote:
On 8/10/2011 12:56 PM, Eric Niebler wrote:
A sequence created by push_back is a Forward Sequence, which means you can't call pop_back on it. I think that's a serious shortcoming. Fusion needs something like MPL's Back Extensible and Front Extensible concepts.
http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/refmanual/back-extensible-...
Unfortunately, this would likely require a redesign of the whole (push|pop)_(front|back) mechanism.
Man, this is a major bummer, alright. One plausible clean way I can think of is:
1) Make single_view random_access (if it's not already; IIRC No).
I implemented this not too long ago.
2) Make joint_view assume the least sequence category of its subsumed sequences. There's already some work done related to this where joint_view inherits the 'associative'-ness of its held sequences.
I don't think that's good enough. Take my example above. In, push_back(nil(), 1), the traversal type of nil is Forward, and so too would be the resulting view. It probably makes sense to see how MPL manages it.
Fusion diverges from MPL in its design in that sequence extension in Fusion always results to an 'extended' view (e.g. joint_view), instead of MPL's sequence-type-preserving operations. That is primarily for the sake of runtime efficiency (e.g. you do not want to have to build a new vector when you push_back an element). For that reason, I do not think it is a good idea to manage it like MPL. That example of yours [ push_back(nil(), 1) ] can also be made to work by making 'nil' random-access. In essence, we should give all sequences the highest potential traversal category that we can. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/10/2011 11:18 AM, Joel de Guzman wrote:
That example of yours [ push_back(nil(), 1) ] can also be made to work by making 'nil' random-access. In essence, we should give all sequences the highest potential traversal category that we can.
OK, let's pick a different example: fusion::list<int> l(1); fusion::pop_back(fusion::push_back(l, 42)); Although technically this works today, it's just a curiosity due to the way joint_view iterators work. list is fwd, so according to your scheme so too would be push_back(l, 42), and so we couldn't legally call pop_back on it. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/11/2011 3:40 AM, Eric Niebler wrote:
On 8/10/2011 11:18 AM, Joel de Guzman wrote:
That example of yours [ push_back(nil(), 1) ] can also be made to work by making 'nil' random-access. In essence, we should give all sequences the highest potential traversal category that we can.
OK, let's pick a different example:
fusion::list<int> l(1); fusion::pop_back(fusion::push_back(l, 42));
Although technically this works today, it's just a curiosity due to the way joint_view iterators work.
Interesting. I wouldn't think that would work. How did that work? list is fwd, so according to your scheme
so too would be push_back(l, 42), and so we couldn't legally call pop_back on it.
Yes, but that's as far as the view concepts can proceed. Anything more will have to be a redesign of Fusion. Again, MPL's design does not fit Fusion's because of the expensive runtime operations involved with 'extensible-sequences'. So, unless you have a better suggestion, that's the best I can offer ATM. Hmmmm. now that I think about it, it is also possible to change the implementation of pop_back to make it so that it would not need to use 'prior'. The end iterator can be abstracted such that it compares equal to i through next(i). I'll see if that works out. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/11/2011 4:04 AM, Joel de Guzman wrote:
Hmmmm. now that I think about it, it is also possible to change the implementation of pop_back to make it so that it would not need to use 'prior'. The end iterator can be abstracted such that it compares equal to i through next(i). I'll see if that works out.
Yep. It works like a charm. I have a fix. Now this works: { list<int, int> l(1, 2); std::cout << pop_back(l) << std::endl; BOOST_TEST((pop_back(l) == make_list(1))); } Now, indeed, the docs works as advertized. Thanks for your nudging, Eric. I truly appreciate it. You get my neurons humming. Committed to trunk. I'd welcome a quick review before I make this official. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/10/2011 3:06 PM, Joel de Guzman wrote:
On 8/11/2011 4:04 AM, Joel de Guzman wrote:
Hmmmm. now that I think about it, it is also possible to change the implementation of pop_back to make it so that it would not need to use 'prior'. The end iterator can be abstracted such that it compares equal to i through next(i). I'll see if that works out.
Yep. It works like a charm. I have a fix. Now this works:
{ list<int, int> l(1, 2); std::cout << pop_back(l) << std::endl; BOOST_TEST((pop_back(l) == make_list(1))); }
Now, indeed, the docs works as advertized.
Thanks for your nudging, Eric. I truly appreciate it. You get my neurons humming. Committed to trunk. I'd welcome a quick review before I make this official.
Very clever! Looks good to me. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/11/2011 12:19 PM, Eric Niebler wrote:
On 8/10/2011 3:06 PM, Joel de Guzman wrote:
On 8/11/2011 4:04 AM, Joel de Guzman wrote:
Hmmmm. now that I think about it, it is also possible to change the implementation of pop_back to make it so that it would not need to use 'prior'. The end iterator can be abstracted such that it compares equal to i through next(i). I'll see if that works out.
Yep. It works like a charm. I have a fix. Now this works:
{ list<int, int> l(1, 2); std::cout << pop_back(l) << std::endl; BOOST_TEST((pop_back(l) == make_list(1))); }
Now, indeed, the docs works as advertized.
Thanks for your nudging, Eric. I truly appreciate it. You get my neurons humming. Committed to trunk. I'd welcome a quick review before I make this official.
Very clever! Looks good to me.
Cool. Now I notice that pop_back_iterator is the workings of a reusable iterator_adapter. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/11/2011 5:08 PM, Joel de Guzman wrote:
On 8/11/2011 12:19 PM, Eric Niebler wrote:
On 8/10/2011 3:06 PM, Joel de Guzman wrote:
On 8/11/2011 4:04 AM, Joel de Guzman wrote:
Hmmmm. now that I think about it, it is also possible to change the implementation of pop_back to make it so that it would not need to use 'prior'. The end iterator can be abstracted such that it compares equal to i through next(i). I'll see if that works out.
Yep. It works like a charm. I have a fix. Now this works:
{ list<int, int> l(1, 2); std::cout << pop_back(l) << std::endl; BOOST_TEST((pop_back(l) == make_list(1))); }
Now, indeed, the docs works as advertized.
Thanks for your nudging, Eric. I truly appreciate it. You get my neurons humming. Committed to trunk. I'd welcome a quick review before I make this official.
Very clever! Looks good to me.
Cool. Now I notice that pop_back_iterator is the workings of a reusable iterator_adapter.
Ok, so now we have a fusion iterator_adapter. pop_back_iterator is the first client. Refactoring + QOI stuff. Docs to follow when i get time in the weekend (note to self). Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On Thu, Aug 11, 2011 at 8:46 AM, Joel de Guzman <joel@boost-consulting.com>wrote:
On 8/11/2011 5:08 PM, Joel de Guzman wrote:
[...]
Cool. Now I notice that pop_back_iterator is the workings of a reusable iterator_adapter.
Ok, so now we have a fusion iterator_adapter. pop_back_iterator is the first client. Refactoring + QOI stuff. Docs to follow when i get time in the weekend (note to self).
Regarding fusion::iterator_adaptor, great! I had rolled my own junk implementation (and used it to implement some move_iterator-like iterators) so it would be good to just pull something from Boost.Fusion. If you want me to share what I had written (mine's relatively simple), let me know. - Jeff
On 8/12/2011 4:04 AM, Jeffrey Lee Hellrung, Jr. wrote:
Regarding fusion::iterator_adaptor, great! I had rolled my own junk implementation (and used it to implement some move_iterator-like iterators) so it would be good to just pull something from Boost.Fusion.
If you want me to share what I had written (mine's relatively simple), let me know.
Sure. I'd love to see your move_iterator-like iterators (if that's what you mean) if you can port it to the new iterator_adaptor thingy. If you mean your own 'iterator_adaptor' implementation, It would be better if you can peruse and review the one in the trunk and tell me if you can suggest improvements (so far, it has not been tested yet). Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On Thu, Aug 11, 2011 at 10:32 PM, Joel de Guzman <joel@boost-consulting.com>wrote:
On 8/12/2011 4:04 AM, Jeffrey Lee Hellrung, Jr. wrote:
Regarding fusion::iterator_adaptor, great! I had rolled my own junk implementation (and used it to implement some move_iterator-like iterators) so it would be good to just pull something from Boost.Fusion.
If you want me to share what I had written (mine's relatively simple), let me know.
Sure. I'd love to see your move_iterator-like iterators (if that's what you mean) if you can port it to the new iterator_adaptor thingy.
Well, it's not what I meant, but I can share those, too. Perhaps better to wait until iterator_adaptor is settled and Ion's Boost.Move is in a release. I have a move_iterator and move_owned_iterator, both using Ion's Move; the latter only moves elements of a sequence whose value_of is a non-reference type.
If you mean your own 'iterator_adaptor' implementation, It would be better if you can peruse and review the one in the trunk and tell me if you can suggest improvements (so far, it has not been tested yet).
Okay, here are the functional differences between our implementations: - I use the category_of metafunction rather than Iterator_::category (I don't recall offhand if a nested ::category is required for Fusion iterators, so these could very well be interchangeable...). - I include a 3rd template parameter, Traversal, which defaults to the Iterator_'s category_of, and allows one to override the traversal category. - I do *not* have default implementations of next, prior, and advance, instead forcing the derived class to implement these, if desired; I notice you require the derived class to implement a make metafunction, which I guess is fine, but then shouldn't iterator_adaptor::advance::call use something like Derived_::make::call, so ultimately put the iterator construction responsibility on the derived class? If so, I'm not sure if providing default implementations of next, prior, and advance is really all that convenient... - I also include default implementations of key_of, value_of_data, and deref_data. - Jeff
On 8/12/2011 2:12 PM, Jeffrey Lee Hellrung, Jr. wrote:
On Thu, Aug 11, 2011 at 10:32 PM, Joel de Guzman <joel@boost-consulting.com>wrote:
On 8/12/2011 4:04 AM, Jeffrey Lee Hellrung, Jr. wrote:
Regarding fusion::iterator_adaptor, great! I had rolled my own junk implementation (and used it to implement some move_iterator-like iterators) so it would be good to just pull something from Boost.Fusion.
If you want me to share what I had written (mine's relatively simple), let me know.
Sure. I'd love to see your move_iterator-like iterators (if that's what you mean) if you can port it to the new iterator_adaptor thingy.
Well, it's not what I meant, but I can share those, too. Perhaps better to wait until iterator_adaptor is settled and Ion's Boost.Move is in a release. I have a move_iterator and move_owned_iterator, both using Ion's Move; the latter only moves elements of a sequence whose value_of is a non-reference type.
Ok.
If you mean your own 'iterator_adaptor' implementation, It would be better if you can peruse and review the one in the trunk and tell me if you can suggest improvements (so far, it has not been tested yet).
Okay, here are the functional differences between our implementations:
- I use the category_of metafunction rather than Iterator_::category (I don't recall offhand if a nested ::category is required for Fusion iterators, so these could very well be interchangeable...).
It is, in the implementation POV. category_of is better though for the sake of struct concept conformance.
- I include a 3rd template parameter, Traversal, which defaults to the Iterator_'s category_of, and allows one to override the traversal category.
Nice idea.
- I do *not* have default implementations of next, prior, and advance, instead forcing the derived class to implement these, if desired; I notice you require the derived class to implement a make metafunction, which I guess is fine, but then shouldn't iterator_adaptor::advance::call use something like Derived_::make::call, so ultimately put the iterator
You are looking at a slightly older version. It's been fixed.
construction responsibility on the derived class? If so, I'm not sure if providing default implementations of next, prior, and advance is really all that convenient...
Consider a transform iterator where you want a next, prior, advance to do as usual, but 'override' the behavior of value_of and deref to do your bidding. In that common case, you do not want to bother with the reimplementations.
- I also include default implementations of key_of, value_of_data, and deref_data.
Good! I'd welcome a merge. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On Thu, Aug 11, 2011 at 11:33 PM, Joel de Guzman <joel@boost-consulting.com>wrote:
On 8/12/2011 2:12 PM, Jeffrey Lee Hellrung, Jr. wrote:
[...]
Okay, here are the functional differences between our implementations:
[...]
- I do *not* have default implementations of next, prior, and advance, instead forcing the derived class to implement these, if desired; I notice you require the derived class to implement a make metafunction, which I guess is fine, but then shouldn't iterator_adaptor::advance::call use something like Derived_::make::call, so ultimately put the iterator
You are looking at a slightly older version. It's been fixed.
Ah, okay...as I don't actually have the trunk checked out, I just used the online browser; I'll go ahead and check out truck.
construction responsibility on the derived class? If so, I'm not sure if providing default implementations of next, prior, and advance is really all that convenient...
Consider a transform iterator where you want a next, prior, advance to do as usual, but 'override' the behavior of value_of and deref to do your bidding. In that common case, you do not want to bother with the reimplementations.
Yeah, after sending that I changed my mind regarding that conclusion; it is indeed more convenient to only implement the factory "make" stuff in the derived class once than write out the boilerplate for all of next, prior, and advance.
- I also include default implementations of key_of, value_of_data, and deref_data.
Good! I'd welcome a merge.
errr...patch? It is really quite trivial (I think...): template< class This > struct key_of : boost::fusion::result_of::key_of< base_type > { }; template< class This > struct value_of_data : boost::fusion::result_of::value_of_data< base_type > { }; template< class This > struct deref_data { typedef typename boost::fusion::result_of::deref_data< base_type
::type type; static type call(This& this_) { return boost::fusion::deref_data(this_.m_base); } };
or key_of< typename This::base_type > ? (Here, base_type is a typedef for
So, as I look at this (pasted from my implementation), I now wonder: Is there a difference between This::base_type and base_type in the above structs? E.g., does it make a difference whether one uses key_of< base_type the underlying iterator you're adapting, i.e., the Iterator_ parameter in your implementation.) - Jeff
On 8/12/2011 2:49 PM, Jeffrey Lee Hellrung, Jr. wrote:
errr...patch? It is really quite trivial (I think...):
[snip]
or key_of< typename This::base_type > ? (Here, base_type is a typedef for
So, as I look at this (pasted from my implementation), I now wonder: Is there a difference between This::base_type and base_type in the above structs? E.g., does it make a difference whether one uses key_of< base_type the underlying iterator you're adapting, i.e., the Iterator_ parameter in your implementation.)
It doesn't make any difference in this case. This::base_type would be needed if base_type was declared in the base (which incedentally is one reason why I did not use the name "base_type" for the base iterator, esp. since we also have the CRTP derived.) Erm, hey, I'd appreciate a patch that would work out of the box without any more editing. Also would you be interested in implementing sequence_adapter? I'd really need that now to solve the issue that started this thread. Views really ought to be implemented in terms of sequence_adapter. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/10/2011 9:19 PM, Eric Niebler wrote:
On 8/10/2011 3:06 PM, Joel de Guzman wrote:
On 8/11/2011 4:04 AM, Joel de Guzman wrote:
Hmmmm. now that I think about it, it is also possible to change the implementation of pop_back to make it so that it would not need to use 'prior'. The end iterator can be abstracted such that it compares equal to i through next(i). I'll see if that works out.
Yep. It works like a charm. I have a fix. Now this works:
{ list<int, int> l(1, 2); std::cout << pop_back(l) << std::endl; BOOST_TEST((pop_back(l) == make_list(1))); }
Now, indeed, the docs works as advertized.
Thanks for your nudging, Eric. I truly appreciate it. You get my neurons humming. Committed to trunk. I'd welcome a quick review before I make this official.
Very clever! Looks good to me.
I wanted to test this, so I tried the following: using namespace boost::fusion; auto vec = make_vector(1, 3.14, "hello"); auto push = push_back(vec, 42); auto pop = pop_back(push); auto i1 = find<int>(pop); auto i2 = find<double>(pop); assert(i1 != end(pop)); assert(i2 != end(pop)); assert(i1 != i2); It doesn't compile for me. I think it should. And I would hope none of the asserts fire. Will that be the case? -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/12/2011 9:08 AM, Eric Niebler wrote:
I wanted to test this, so I tried the following:
using namespace boost::fusion; auto vec = make_vector(1, 3.14, "hello"); auto push = push_back(vec, 42); auto pop = pop_back(push);
auto i1 = find<int>(pop); auto i2 = find<double>(pop);
assert(i1 != end(pop)); assert(i2 != end(pop)); assert(i1 != i2);
It doesn't compile for me. I think it should. And I would hope none of the asserts fire. Will that be the case?
I think so. It's most probably a bug in the implementation. I'll go check it out. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/12/2011 9:24 AM, Joel de Guzman wrote:
On 8/12/2011 9:08 AM, Eric Niebler wrote:
I wanted to test this, so I tried the following:
using namespace boost::fusion; auto vec = make_vector(1, 3.14, "hello"); auto push = push_back(vec, 42); auto pop = pop_back(push);
auto i1 = find<int>(pop); auto i2 = find<double>(pop);
assert(i1 != end(pop)); assert(i2 != end(pop)); assert(i1 != i2);
It doesn't compile for me. I think it should. And I would hope none of the asserts fire. Will that be the case?
I think so. It's most probably a bug in the implementation. I'll go check it out.
It's fixed. It was a pop_back_iterator bug indeed. I reverted to the original implementation but used advance<begin, size-1> instead of prior. pop_back_iterator is an unwieldy hack and while it might be fixable, I am not sure if its CT cost outweigh the CT cost of simply using advance<begin, size-1>. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/11/2011 10:26 PM, Joel de Guzman wrote:
I reverted to the original implementation but used advance<begin, size-1> instead of prior. pop_back_iterator is an unwieldy hack and while it might be fixable, I am not sure if its CT cost outweigh the CT cost of simply using advance<begin, size-1>.
Yowsa! That instantiates O(N) templates for what should be an O(1) operation. I say leave it as prior until we can think of something better. -- Eric Niebler BoostPro Computing http://www.boostpro.com
On 8/12/2011 2:50 PM, Eric Niebler wrote:
On 8/11/2011 10:26 PM, Joel de Guzman wrote:
I reverted to the original implementation but used advance<begin, size-1> instead of prior. pop_back_iterator is an unwieldy hack and while it might be fixable, I am not sure if its CT cost outweigh the CT cost of simply using advance<begin, size-1>.
Yowsa! That instantiates O(N) templates for what should be an O(1) operation. I say leave it as prior until we can think of something better.
Yeah, you are right. Reverted for now. Alas, the tests will fail, but anyway, I think I know a good strategy to make it work. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
On 8/12/2011 3:25 PM, Joel de Guzman wrote:
On 8/12/2011 2:50 PM, Eric Niebler wrote:
On 8/11/2011 10:26 PM, Joel de Guzman wrote:
I reverted to the original implementation but used advance<begin, size-1> instead of prior. pop_back_iterator is an unwieldy hack and while it might be fixable, I am not sure if its CT cost outweigh the CT cost of simply using advance<begin, size-1>.
Yowsa! That instantiates O(N) templates for what should be an O(1) operation. I say leave it as prior until we can think of something better.
Yeah, you are right. Reverted for now. Alas, the tests will fail, but anyway, I think I know a good strategy to make it work.
Back on track. Now my code is working fine again. All your test code pass just fine. I think I got it right this time. Regards, -- Joel de Guzman http://www.boostpro.com http://boost-spirit.com
participants (3)
-
Eric Niebler -
Jeffrey Lee Hellrung, Jr. -
Joel de Guzman