jbaldwin
Lost values when combined with std::views::take
Not sure if that's a bug or a feature.
Consider the following program (using libcoro from v0.11.1 and main):
#include <coro/coro.hpp>
#include <ranges>
#include <iostream>
coro::generator<size_t> Naturals() {
auto n = 0z;
while (true) {
++n;
co_yield n;
}
}
int main() {
auto n = Naturals();
for (auto i : n | std::views::take(3))
std::cout << i << ' ';
std::cout << '\n';
for (auto i : n | std::views::take(3))
std::cout << i << ' ';
std::cout << '\n';
}
It prints the following:
1 2 3
5 6 7
I expect:
1 2 3
4 5 6
Note: 4 is missing.
If I try std::generator in GCC-14, then it fails to find operator| -- such composition is not even accepted.
Any ideas?
I replaced coro::generator with std::views::iota and it seems that operator| consumes the range by copy:
int main() {
auto n = std::views::iota(1);
for (auto i : n | std::views::take(3))
std::cout << i << ' '; // 1 2 3
std::cout << '\n';
for (auto i : n | std::views::take(3))
std::cout << i << ' '; // 1 2 3
std::cout << '\n';
}
Meanwhile std::generator and coro::generator do not allow copies (how hard would it be to support copies?) and hence std::generator& | std::views::take fails, but it works on rvalue-references.
So maybe coro::generator& | std::views::take should not be allowed as it gives unexpected results like in the original report -- unsafe. Albeit it would still be nice to bind by lvalue reference and then issue a friendly error message with static_assert (not just "failed to find operator|" which appears as incomplete functionality).
Alternatively, std::views::take could be fixed not to request more values than necessary.
Currently it requests one too many values and thus puts the generator into a unexpected state.
Not sure how other adapters are affected.
Hey @mikucionisaau been a busy week, I'll try and take a look at this as soon as I can. Thanks for reporting the issue.
Here is my replacement for std::views::take using coro::generator:
namespace coro {
template <std::ranges::input_range Range,
typename Item = std::iter_value_t<std::ranges::iterator_t<Range>>>
coro::generator<Item> take(Range&& range, size_t count) {
auto it = std::ranges::begin(range);
auto e = std::ranges::end(range);
if (count-->0 && it != e)
co_yield *it;
while (count-->0 && ++it != e)
co_yield *it;
}
struct take_adapter { size_t count; };
take_adapter take(size_t count) { return take_adapter{count}; }
template <std::ranges::input_range Range>
auto operator|(Range&& range, take_adapter& adapter) {
return take(std::forward<Range>(range), adapter.count);
}
template <std::ranges::input_range Range>
auto operator|(Range&& range, take_adapter&& adapter) {
return take(std::forward<Range>(range), adapter.count);
}
}
Coroutine is a bit of an overkill here, but you can see where std::views::take can take one too many.
GCC-13 std::views::take uses counted_iterator, which has overly simple increment operators at stl_iterator.h:2418: it increments the iterator despite the counter reaching zero. Counter reaching 0 means "one passed the range" (just like std::end), but in case of generators it means fetching one more value which is then discarded:
constexpr counted_iterator&
operator++()
{
__glibcxx_assert(_M_length > 0);
++_M_current;
--_M_length;
return *this;
}
A simple fix would be to add an if branching statement, but that hinders performance :-(
Apologies on the very slow response, life has been busy, do you have a possible PR you could push that fixes this?
@jbaldwin the problem is the design decision, what do you prefer?
-
kill the bug by not supporting such case (disable the copy constructor just like
libstdc++does forstd::views::iota). -
fix this corner case by adding an extra
ifcheck tocounted_iterator::operator++()inlibstdc++. -
fix this corner case by providing a sophisticated check for this corner case leaving the default case fast in libstdc++.
The first option is easy, but it is ugly: it does not support trivial use cases like above and the error message is going to be obscure.
The second option may slow down significantly the default case due to extra if branching.
The third option would be the ideal, but it is complicated and involves tinkering with libstdc++, which uses some tricks that I do not understand (like moving a generator into take adapter while preserving ownership within the ranged-for-loop).
The above proposes to replace std::views::take with custom implementation using libcoro generator instead of counted_iterator... which is a massive overkill: it uses while branching and generator boiler plate.
Hmm, I'm oddly inclined towards option 1 with hopefully a good error message since its how the stdlib solved a similar problem but some thoughts on 2 and 3:
-
Seems pretty un-ideal since it hurts every other use case.
-
I'm not sure I have time to solve this right now, but if you had a solution I would be willing to accept it.
I looked at coro::generator and found that the copy constructor/assignment are already deleted.
I still cannot understand how std::generator is rejected while coro::generator is accepted when passed by lvalue reference.
// range | adaptor is equivalent to adaptor(range).
template<typename _Self, typename _Range>
requires __is_range_adaptor_closure<_Self>
&& __adaptor_invocable<_Self, _Range>
constexpr auto
operator|(_Range&& __r, _Self&& __self)
{ return std::forward<_Self>(__self)(std::forward<_Range>(__r)); }
The call operator constructs an instance of take_view:
struct _Take : __adaptor::_RangeAdaptor<_Take>
{
template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
requires __detail::__can_take_view<_Range, _Dp>
constexpr auto
operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
{
using _Tp = remove_cvref_t<_Range>;
if constexpr (__detail::__is_empty_view<_Tp>)
[...]
else
return take_view(std::forward<_Range>(__r), __n);
}
Deduction guide for take_view wraps the generator type into ref_view by applying std::views::all_t:
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3447. Deduction guides for take_view and drop_view have different
// constraints
template<typename _Range>
take_view(_Range&&, range_difference_t<_Range>)
-> take_view<views::all_t<_Range>>;
Which creates a ref_view holding onto a pointer to our generator:
template<range _Range> requires is_object_v<_Range>
class ref_view : public view_interface<ref_view<_Range>>
{
private:
_Range* _M_r;
static void _S_fun(_Range&); // not defined
static void _S_fun(_Range&&) = delete;
public:
template<__detail::__different_from<ref_view> _Tp>
requires convertible_to<_Tp, _Range&>
&& requires { _S_fun(declval<_Tp>()); }
constexpr
ref_view(_Tp&& __t)
noexcept(noexcept(static_cast<_Range&>(std::declval<_Tp>())))
: _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t))))
{ }
Eventually the constructor of take_view is called:
template<view _Vp>
class take_view : public view_interface<take_view<_Vp>>
{
private:
[...]
_Vp _M_base = _Vp();
range_difference_t<_Vp> _M_count = 0;
public:
[...]
constexpr
take_view(_Vp __base, range_difference_t<_Vp> __count)
: _M_base(std::move(__base)), _M_count(std::move(__count))
{ }
The ref_view with a pointer is then moved into this take_view.
Basically ref_view works around the deleted copy constructor of coro::generator. But the same is true for std::generator.
Based on the above, I have created a bunch of checks for std::generator and it passes them all(!):
auto n = StdNaturals();
using gen_type = decltype(n);
static_assert(std::ranges::range<gen_type>, "is not a range");
static_assert(std::is_object_v<gen_type>, "is not an object");
static_assert(std::ranges::viewable_range<gen_type>, "is not viewable");
using gen_diff = std::ranges::range_difference_t<gen_type>;
gen_diff gd;
static_assert(std::ranges::range<gen_type>, "is not range");
static_assert(std::ranges::view<std::remove_cvref_t<gen_type>>, "is not view");
static_assert(std::constructible_from<std::remove_cvref_t<gen_type>, gen_type>, "not constructible");
So it is still a mystery for me why std::generator lvalue reference is not accepted by std::views::take but coro::generator is accepted, therefore I cannot add something to it which would be rejected by std::views::take.
I can't even come up with "simple" solution, sorry :-(
Found one predicate which distinguishes the generators:
auto sn = StdNaturals();
static_assert(std::ranges::view<decltype(sn)>, "is not a view"); // passes
auto cn = CoroNaturals();
static_assert(std::ranges::view<decltype(cn)>, "is not a view"); // fails
then std::ranges::view is defined as:
template<class T>
concept view = ranges::range<T> && std::movable<T> && ranges::enable_view<T>;
range and movable are satisfied by both, meanwhile enable_view is present only in std::generator.
enable_view:
template<typename _Tp>
inline constexpr bool enable_view = derived_from<_Tp, view_base>
|| __detail::__is_derived_from_view_interface<_Tp>;
Basically, the coro::generator needs to inherit from std:ranges::view_base to be treated just like std::generator (then std::views::take does not wrap it into copyable ref_view with a pointer).
Here is the solution patch to disable pass-by-lvalue reference:
diff --git a/include/coro/generator.hpp b/include/coro/generator.hpp
index 5fba1d0..a15305a 100644
--- a/include/coro/generator.hpp
+++ b/include/coro/generator.hpp
@@ -118,7 +118,7 @@ private:
} // namespace detail
template<typename T>
-class generator
+class generator : public std::ranges::view_base
{
public:
using promise_type = detail::generator_promise<T>;
I cannot really add a test for this "feature", because it requires that the compiler fails on it. Very weird.